1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
|
<!doctype html public "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>
<TITLE>nevrax.org : docs</TITLE>
<LINK REL=stylesheet TYPE="text/css" HREF="http://www.nevrax.org/inc/css/nevrax.css">
<link href="doxygen.css" rel="stylesheet" type="text/css">
</HEAD>
<BODY MARGINHEIGHT="0" MARGINWIDTH="0">
<!-- uplinks -->
<TABLE CELLSPACING=0 CELLPADDING=0 BORDER=0>
<TR>
<TD WIDTH=16><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="16" HEIGHT="16" BORDER=0 ALT=""></TD>
<TD WIDTH=140 BGCOLOR=#dddddd><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="140" HEIGHT="16" BORDER=0 ALT=""></TD>
<TD WIDTH=16><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="16" HEIGHT="16" BORDER=0 ALT=""></TD>
<TD><IMG width=6 height=14 SRC="http://www.nevrax.org/inc/img/reddots.gif" ALT="#" VSPACE=2 HSPACE=2 BORDER=0 ></TD><TD VALIGN=middle> <A CLASS=uplinks HREF=http://www.nevrax.org><b>Home</B></FONT></A> </TD>
<TD><IMG width=6 height=14 SRC="http://www.nevrax.org/inc/img/reddots.gif" ALT="#" VSPACE=2 HSPACE=2 BORDER=0 ></TD><TD VALIGN=middle> <A CLASS=uplinks HREF=http://www.nevrax.com><b>nevrax.com</B></FONT></A> </TD>
</TR>
</TABLE>
<!-- banner Nevrax -->
<TABLE CELLSPACING=0 CELLPADDING=0 BORDER=0 WIDTH=100%>
<TR><TD BGCOLOR="#000000" BACKGROUND="http://www.nevrax.org/inc/img/black_banner.jpg"><A HREF="http://www.nevrax.org"><IMG SRC="http://www.nevrax.org/inc/img/nevrax.gif" WIDTH="170" HEIGHT="45" BORDER=0 ALT="Nevrax" ></A></TD></TR>
</TABLE>
<!-- main table -->
<TABLE CELLSPACING=0 CELLPADDING=0 BORDER=0 height=100%>
<TR>
<TD WIDTH=16><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="16" HEIGHT="10" BORDER=0 ALT=""></TD>
<TD WIDTH=140 BGCOLOR=#dddddd VALIGN=TOP ALIGN=middle><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="140" HEIGHT="10" BORDER=0 ALT="">
<!------ Begin Box ------>
<TABLE BORDER=0 CELLSPACING=0 CELLPADDING=0 BGCOLOR=black><TR><TD><TABLE border=0 cellspacing=2 cellpadding=0 width=120><tr><TD ALIGN=middle bgcolor=black>
<FONT COLOR=white FACE="sans-serif"><B>Nevrax.org</B></FONT></TD></TR><tr><td colspan=2 bgcolor=#FFFFFF>
<TABLE cellspacing=0 cellpadding=1 border=0>
<tr><td ALIGN=middle><a class='linkbox' href="http://www.nevrax.org/news/" TITLE="Rubrique news"><img width=13 height=15 hspace=5 border=0 src=http://www.nevrax.org/inc/img/picto-news.gif ALT=#></A></td><td><a class='linkbox' href="http://www.nevrax.org/news/" TITLE="News">News</a></td></tr>
<tr><td ALIGN=middle><a class='linkbox' href="http://www.nevrax.org/mail/" TITLE="Rubrique mail"><img width=15 height=11 hspace=5 border=0 src=http://www.nevrax.org/inc/img/picto-mail.gif ALT=#></A></td><td><a class='linkbox' href="http://www.nevrax.org/mail/" TITLE="Mailing list archive">Mailing-list</a></td></tr>
<tr><td ALIGN=middle><a class='linkbox' href="http://www.nevrax.org/docs/" TITLE="Rubrique docs"><img width=14 height=16 hspace=5 border=0 src=http://www.nevrax.org/inc/img/picto-docs.gif ALT=#></A></td><td><a class='linkbox' href="http://www.nevrax.org/docs/" TITLE="Documentation">Documentation</a></td></tr>
<tr><td ALIGN=middle><a class='linkbox' href="http://www.nevrax.org/cvs/" TITLE="Rubrique cvs"><img width=13 height=17 hspace=5 border=0 src=http://www.nevrax.org/inc/img/picto-cvs.gif ALT=#></A></td><td><a class='linkbox' href="http://www.nevrax.org/cvs/" TITLE="CVS Web">CVS</a></td></tr>
<tr><td ALIGN=middle><a class='linkbox' href="http://www.nevrax.org/bugs/" TITLE="Rubrique bugs"><img width=20 height=16 hspace=5 border=0 src=http://www.nevrax.org/inc/img/picto-bugs.gif ALT=#></A></td><td><a class='linkbox' href="http://www.nevrax.org/bugs/" TITLE="Bugtracking">Bugs</a></td></tr>
<tr><td ALIGN=middle><a class='linkbox' href="http://www.nevrax.org/GPL.php3" TITLE="Rubrique license"><img width=18 height=12 hspace=5 border=0 src=http://www.nevrax.org/inc/img/picto-gpl.gif ALT=#></A></td><td><a class='linkbox' href="http://www.nevrax.org/GPL.php3" TITLE="License">License</a></td></tr>
</TABLE>
</TD></TR></TABLE></TD></TR></TABLE>
<!------ End Box ------>
</TD>
<TD WIDTH=15><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="16" HEIGHT="16" BORDER=0 ALT=""></TD>
<TD ALIGN=left valign=top><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="140" HEIGHT="10" BORDER=0 ALT="">
<!-- title -->
<TABLE background="http://www.nevrax.org/inc/img/redline.gif" CELLSPACING=0 CELLPADDING=0 BORDER=0 width=100%><tr><td>
<A HREF="http://www.nevrax.org/docs/"><img src="http://www.nevrax.org/inc/img/t_docs.gif" ALT="Docs" HEIGHT=20 BORDER=0></A>
</td><td><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="1" HEIGHT="1" BORDER=0 ALT="">
</td></tr></table>
<!-- block -->
<TABLE bgcolor="#dddddd" CELLSPACING=0 CELLPADDING=0 BORDER=0 width=100%><tr><td width=1% valign=middle><img width=6 height=14 hspace=2 vspace=2 src="http://www.nevrax.org/inc/img/reddots.gif"></TD>
<TD><B>Documentation</B></TD>
<TD ALIGN=RIGHT> </td>
</tr></table>
<!-- Generated by Doxygen 1.2.14 -->
<center>
<a class="qindex" href="index.html">Main Page</a> <a class="qindex" href="namespaces.html">Namespace List</a> <a class="qindex" href="hierarchy.html">Class Hierarchy</a> <a class="qindex" href="classes.html">Alphabetical List</a> <a class="qindex" href="annotated.html">Compound List</a> <a class="qindex" href="files.html">File List</a> <a class="qindex" href="namespacemembers.html">Namespace Members</a> <a class="qindex" href="functions.html">Compound Members</a> <a class="qindex" href="globals.html">File Members</a> <a class="qindex" href="pages.html">Related Pages</a> <a class="qindexRef" doxygen="_cgi:http://www.nevrax.org/cgi-bin/nel-search.cgi" href="http://www.nevrax.org/cgi-bin/nel-search.cgi">Search</a> </center>
<hr><h1>edge_collide.cpp</h1><a href="edge__collide_8cpp.html">Go to the documentation of this file.</a><div class="fragment"><pre>00001
00007 <font class="comment">/* Copyright, 2001 Nevrax Ltd.</font>
00008 <font class="comment"> *</font>
00009 <font class="comment"> * This file is part of NEVRAX NEL.</font>
00010 <font class="comment"> * NEVRAX NEL is free software; you can redistribute it and/or modify</font>
00011 <font class="comment"> * it under the terms of the GNU General Public License as published by</font>
00012 <font class="comment"> * the Free Software Foundation; either version 2, or (at your option)</font>
00013 <font class="comment"> * any later version.</font>
00014 <font class="comment"></font>
00015 <font class="comment"> * NEVRAX NEL is distributed in the hope that it will be useful, but</font>
00016 <font class="comment"> * WITHOUT ANY WARRANTY; without even the implied warranty of</font>
00017 <font class="comment"> * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU</font>
00018 <font class="comment"> * General Public License for more details.</font>
00019 <font class="comment"></font>
00020 <font class="comment"> * You should have received a copy of the GNU General Public License</font>
00021 <font class="comment"> * along with NEVRAX NEL; see the file COPYING. If not, write to the</font>
00022 <font class="comment"> * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,</font>
00023 <font class="comment"> * MA 02111-1307, USA.</font>
00024 <font class="comment"> */</font>
00025
00026 <font class="preprocessor">#include "<a class="code" href="stdpacs_8h.html">stdpacs.h</a>"</font>
00027
00028 <font class="preprocessor">#include "<a class="code" href="edge__collide_8h.html">pacs/edge_collide.h</a>"</font>
00029
00030 <font class="keyword">using</font> <font class="keyword">namespace </font>NLMISC;
00031 <font class="keyword">using</font> <font class="keyword">namespace </font>std;
00032
00033
00034
00035 <font class="keyword">namespace </font>NLPACS
00036 {
00037
00038
00039 <font class="keyword">static</font> <font class="keyword">const</font> <font class="keywordtype">float</font> <a class="code" href="namespaceNLPACS.html#a6">EdgeCollideEpsilon</a>= 1e-5f;
00040
00041
00042 <font class="comment">// ***************************************************************************</font>
<a name="l00043"></a><a class="code" href="classNLPACS_1_1CEdgeCollide.html#a0">00043</a> <font class="keywordtype">void</font> CEdgeCollide::make(<font class="keyword">const</font> CVector2f &p0, <font class="keyword">const</font> CVector2f &p1)
00044 {
00045 <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>= p0;
00046 <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m1">P1</a>= p1;
00047 <font class="comment">// translation axis of the edge.</font>
00048 <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m2">Dir</a>= <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m1">P1</a>-<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>;
00049 <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m2">Dir</a>.normalize();
00050 <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m4">A0</a>= <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>*<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m2">Dir</a>;
00051 <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m5">A1</a>= <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m1">P1</a>*<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m2">Dir</a>;
00052 <font class="comment">// line equation.</font>
00053 <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m3">Norm</a>.x= <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m2">Dir</a>.y;
00054 <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m3">Norm</a>.y= -<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m2">Dir</a>.x;
00055 <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m6">C</a>= - <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>*<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m3">Norm</a>;
00056 }
00057
00058
00059 <font class="comment">// ***************************************************************************</font>
<a name="l00060"></a><a class="code" href="classNLPACS_1_1CEdgeCollide.html#a1">00060</a> CRational64 CEdgeCollide::testPointMove(<font class="keyword">const</font> CVector2f &start, <font class="keyword">const</font> CVector2f &end, TPointMoveProblem &moveBug)
00061 {
00062 <font class="comment">/*</font>
00063 <font class="comment"> To have a correct test (with no float precision problem):</font>
00064 <font class="comment"> - test first if there is collision beetween the 2 edges:</font>
00065 <font class="comment"> - test if first edge collide the other line.</font>
00066 <font class="comment"> - test if second edge collide the other line.</font>
00067 <font class="comment"> - if both true, yes, there is a collision.</font>
00068 <font class="comment"> - compute time of collision.</font>
00069 <font class="comment"> */</font>
00070
00071
00072 <font class="comment">// *this must be a correct edge.</font>
00073 <font class="keywordflow">if</font>(<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>==<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m1">P1</a>)
00074 {
00075 moveBug= <a class="code" href="classNLPACS_1_1CEdgeCollide.html#s6s4">EdgeNull</a>;
00076 <font class="keywordflow">return</font> -1;
00077 }
00078
00079 <font class="comment">// if no movement, no collision.</font>
00080 <font class="keywordflow">if</font>(start==end)
00081 <font class="keywordflow">return</font> 1;
00082
00083 <font class="comment">// NB those edges are snapped (1/256 for edgeCollide, and 1/1024 for start/end), so no float problem here.</font>
00084 <font class="comment">// precision is 20 bits.</font>
00085 CVector2f normEdge;
00086 CVector2f normMove;
00087 CVector2f deltaEdge;
00088 CVector2f deltaMove;
00089
00090 <font class="comment">// compute normal of the edge (not normalized, because no need, and for precision problem).</font>
00091 deltaEdge= <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m1">P1</a>-<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>;
00092 normEdge.x= -deltaEdge.y;
00093 normEdge.y= deltaEdge.x;
00094
00095 <font class="comment">// compute normal of the movement (not normalized, because no need, and for precision problem).</font>
00096 deltaMove= end-start;
00097 normMove.x= -deltaMove.y;
00098 normMove.y= deltaMove.x;
00099
00100 <font class="comment">// distance from points of movment against edge line. Use double, because of multiplication.</font>
00101 <font class="comment">// precision is now 43 bits.</font>
00102 <font class="keywordtype">double</font> moveD0= (double)normEdge.x*(double)(start.x-<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>.x) + (double)normEdge.y*(double)(start.y-<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>.y);
00103 <font class="keywordtype">double</font> moveD1= (double)normEdge.x*(double)(end.x -<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>.x) + (double)normEdge.y*(double)(end.y -<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>.y);
00104
00105 <font class="comment">// distance from points of edge against movement line. Use double, because of multiplication.</font>
00106 <font class="comment">// precision is now 43 bits.</font>
00107 <font class="keywordtype">double</font> edgeD0= (double)normMove.x*(double)(<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>.x-start.x) + (double)normMove.y*(double)(<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>.y-start.y);
00108 <font class="keywordtype">double</font> edgeD1= (double)normMove.x*(double)(<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m1">P1</a>.x-start.x) + (double)normMove.y*(double)(<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m1">P1</a>.y-start.y);
00109
00110
00111 <font class="comment">// If both edges intersect lines (including endpoints), there is a collision, else none.</font>
00112 sint sgnMove0, sgnMove1;
00113 sgnMove0= <a class="code" href="namespaceNLMISC.html#a213">fsgn</a>(moveD0);
00114 sgnMove1= <a class="code" href="namespaceNLMISC.html#a213">fsgn</a>(moveD1);
00115
00116 <font class="comment">// special case if the 2 edges lies on the same line.</font>
00117 <font class="keywordflow">if</font>(sgnMove0==0 && sgnMove1==0)
00118 {
00119 <font class="comment">// must test if there is a collision. if yes, problem.</font>
00120 <font class="comment">// project all the points on the line of the edge.</font>
00121 <font class="comment">// Use double because of multiplication. precision is now 43 bits.</font>
00122 <font class="keywordtype">double</font> moveA0= (double)deltaEdge.x*(double)(start.x-<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>.x) + (double)deltaEdge.y*(double)(start.y-<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>.y);
00123 <font class="keywordtype">double</font> moveA1= (double)deltaEdge.x*(double)(end.x -<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>.x) + (double)deltaEdge.y*(double)(end.y -<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>.y);
00124 <font class="keywordtype">double</font> edgeA0= 0;
00125 <font class="keywordtype">double</font> edgeA1= (double)deltaEdge.x*(double)deltaEdge.x + (double)deltaEdge.y*(double)deltaEdge.y;
00126
00127 <font class="comment">// Test is there is intersection (endpoints included). if yes, return -1. else return 1 (no collision at all).</font>
00128 <font class="keywordflow">if</font>(moveA1>=edgeA0 && edgeA1>=moveA0)
00129 {
00130 moveBug= <a class="code" href="classNLPACS_1_1CEdgeCollide.html#s6s0">ParallelEdges</a>;
00131 <font class="keywordflow">return</font> -1;
00132 }
00133 <font class="keywordflow">else</font>
00134 <font class="keywordflow">return</font> 1;
00135 }
00136
00137 <font class="comment">// if on same side of the line=> there is no collision.</font>
00138 <font class="keywordflow">if</font>( sgnMove0==sgnMove1)
00139 <font class="keywordflow">return</font> 1;
00140
00141 <font class="comment">// test edge against move line.</font>
00142 sint sgnEdge0, sgnEdge1;
00143 sgnEdge0= <a class="code" href="namespaceNLMISC.html#a213">fsgn</a>(edgeD0);
00144 sgnEdge1= <a class="code" href="namespaceNLMISC.html#a213">fsgn</a>(edgeD1);
00145
00146 <font class="comment">// should not have this case, because tested before with (sgnMove==0 && sgnMove1==0).</font>
00147 <a class="code" href="debug_8h.html#a6">nlassert</a>(sgnEdge0!=0 || sgnEdge1!=0);
00148
00149
00150 <font class="comment">// if on same side of the line, no collision against this edge.</font>
00151 <font class="keywordflow">if</font>( sgnEdge0==sgnEdge1 )
00152 <font class="keywordflow">return</font> 1;
00153
00154 <font class="comment">// Here the edges intersect, but ensure that there is no limit problem.</font>
00155 <font class="keywordflow">if</font>(sgnEdge0==0 || sgnEdge1==0)
00156 {
00157 moveBug= <a class="code" href="classNLPACS_1_1CEdgeCollide.html#s6s3">TraverseEndPoint</a>;
00158 <font class="keywordflow">return</font> -1;
00159 }
00160 <font class="keywordflow">else</font> <font class="keywordflow">if</font>(sgnMove1==0)
00161 {
00162 moveBug= <a class="code" href="classNLPACS_1_1CEdgeCollide.html#s6s2">StopOnEdge</a>;
00163 <font class="keywordflow">return</font> -1;
00164 }
00165 <font class="keywordflow">else</font> <font class="keywordflow">if</font>(sgnMove0==0)
00166 {
00167 <font class="comment">// this should not arrive.</font>
00168 moveBug= <a class="code" href="classNLPACS_1_1CEdgeCollide.html#s6s1">StartOnEdge</a>;
00169 <font class="keywordflow">return</font> -1;
00170 }
00171
00172
00173 <font class="comment">// Here, there is a normal collision, just compute it.</font>
00174 <font class="comment">// Because of Division, there is a precision lost in double. So compute a CRational64.</font>
00175 <font class="comment">// First, compute numerator and denominator in the highest precision. this is 1024*1024 because of prec multiplication.</font>
00176 <font class="keywordtype">double</font> numerator= (0-moveD0)*1024*1024;
00177 <font class="keywordtype">double</font> denominator= (moveD1-moveD0)*1024*1024;
00178 sint64 numeratorInt= (sint64)numerator;
00179 sint64 denominatorInt= (sint64)denominator;
00180 <font class="comment">/*</font>
00181 <font class="comment"> nlassert(numerator == numeratorInt);</font>
00182 <font class="comment"> nlassert(denominator == denominatorInt);</font>
00183 <font class="comment">*/</font>
00184 <font class="keywordflow">if</font> (numerator != numeratorInt)
00185 <a class="code" href="debug_8h.html#a2">nlwarning</a>(<font class="stringliteral">"numerator(%f) != numeratorInt(%"</font>NL_I64<font class="stringliteral">"d)"</font>, numerator, numeratorInt);
00186 <font class="keywordflow">if</font> (denominator != denominatorInt)
00187 <a class="code" href="debug_8h.html#a2">nlwarning</a>(<font class="stringliteral">"denominator(%f) != denominatorInt(%"</font>NL_I64<font class="stringliteral">"d)"</font>, denominator, denominatorInt);
00188
00189 <font class="keywordflow">return</font> CRational64(numeratorInt, denominatorInt);
00190 }
00191
00192
00193 <font class="comment">// ***************************************************************************</font>
00194 <font class="keyword">static</font> <font class="keyword">inline</font> <font class="keywordtype">float</font> <a class="code" href="namespaceNLPACS.html#a26">testCirclePoint</a>(<font class="keyword">const</font> CVector2f &start, <font class="keyword">const</font> CVector2f &delta, <font class="keywordtype">float</font> radius, <font class="keyword">const</font> CVector2f &point)
00195 {
00196 <font class="comment">// factors of the qaudratic: at� + bt + c=0</font>
00197 <font class="keywordtype">float</font> a,b,c;
00198 <font class="keywordtype">float</font> dta;
00199 <font class="keywordtype">float</font> r0, r1, <a class="code" href="driver__opengl__extension__def_8h.html#a400">res</a>;
00200 CVector2f relC, relV;
00201
00202 <font class="comment">// compute quadratic..</font>
00203 relC= start-point;
00204 relV= delta;
00205 a= relV.x*relV.x + relV.y*relV.y; <font class="comment">// a>=0.</font>
00206 b= 2* (relC.x*relV.x + relC.y*relV.y);
00207 c= relC.x*relC.x + relC.y*relC.y - radius*radius;
00208 <font class="comment">// compute delta of the quadratic.</font>
00209 dta= b*b - 4*a*c; <font class="comment">// b�-4ac</font>
00210 <font class="keywordflow">if</font>(dta>=0)
00211 {
00212 dta= (float)sqrt(dta);
00213 r0= (-b -dta)/(2*a);
00214 r1= (-b +dta)/(2*a);
00215 <font class="comment">// since a>0, r0<=r1.</font>
00216 <font class="keywordflow">if</font>(r0>r1)
00217 swap(r0,r1);
00218 <font class="comment">// if r1 is negative, then we are out and go away from this point. OK.</font>
00219 <font class="keywordflow">if</font>(r1<=0)
00220 {
00221 <a class="code" href="driver__opengl__extension__def_8h.html#a400">res</a>= 1;
00222 }
00223 <font class="comment">// if r0 is positive, then we may collide this point.</font>
00224 <font class="keywordflow">else</font> <font class="keywordflow">if</font>(r0>=0)
00225 {
00226 <a class="code" href="driver__opengl__extension__def_8h.html#a400">res</a>= <a class="code" href="bit__set_8cpp.html#a0">min</a>(1.f, r0);
00227 }
00228 <font class="keywordflow">else</font> <font class="comment">// r0<0 && r1>0. the point is already in the sphere!!</font>
00229 {
00230 <font class="comment">//nlinfo("COL: Point problem: %.2f, %.2f. b=%.2f", r0, r1, b);</font>
00231 <font class="comment">// we allow the movement only if we go away from this point.</font>
00232 <font class="comment">// this is true if the derivative at t=0 is >=0 (because a>0).</font>
00233 <font class="keywordflow">if</font>(b>0)
00234 <a class="code" href="driver__opengl__extension__def_8h.html#a400">res</a>= 1; <font class="comment">// go out.</font>
00235 <font class="keywordflow">else</font>
00236 <a class="code" href="driver__opengl__extension__def_8h.html#a400">res</a>=0;
00237 }
00238 }
00239 <font class="keywordflow">else</font>
00240 {
00241 <font class="comment">// never hit this point along this movement.</font>
00242 <a class="code" href="driver__opengl__extension__def_8h.html#a400">res</a>= 1;
00243 }
00244
00245 <font class="keywordflow">return</font> <a class="code" href="driver__opengl__extension__def_8h.html#a400">res</a>;
00246 }
00247
00248
00249 <font class="comment">// ***************************************************************************</font>
<a name="l00250"></a><a class="code" href="classNLPACS_1_1CEdgeCollide.html#a2">00250</a> <font class="keywordtype">float</font> CEdgeCollide::testCircleMove(<font class="keyword">const</font> CVector2f &start, <font class="keyword">const</font> CVector2f &delta, <font class="keywordtype">float</font> radius, CVector2f &normal)
00251 {
00252 <font class="comment">// distance from point to line.</font>
00253 <font class="keywordtype">double</font> dist= start*<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m3">Norm</a> + <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m6">C</a>;
00254 <font class="comment">// projection of speed on normal.</font>
00255 <font class="keywordtype">double</font> speed= delta*<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m3">Norm</a>;
00256
00257 <font class="comment">// test if the movement is against the line or not.</font>
00258 <font class="keywordtype">bool</font> sensPos= dist>0;
00259 <font class="keywordtype">bool</font> sensSpeed= speed>0;
00260
00261 <font class="comment">// Does the point intersect the line?</font>
00262 dist= fabs(dist) - radius;
00263 speed= fabs(speed);
00264 <font class="keywordflow">if</font>( dist > speed )
00265 <font class="keywordflow">return</font> 1;
00266
00267 <font class="comment">// if not already in collision with the line, test when it collides.</font>
00268 <font class="comment">// ===============================</font>
00269 <font class="keywordflow">if</font>(dist>=0)
00270 {
00271 <font class="comment">// if signs are equals, same side of the line, so we allow the circle to leave the line.</font>
00272 <font class="keywordflow">if</font>(sensPos==sensSpeed )
00273 <font class="keywordflow">return</font> 1;
00274
00275 <font class="comment">// collide the line, at what time.</font>
00276 <font class="keywordtype">double</font> <a class="code" href="driver__opengl__extension__def_8h.html#a384">t</a>= dist/speed;
00277
00278
00279 <font class="comment">// compute the collision position of the Circle on the edge.</font>
00280 <font class="comment">// this gives the center of the sphere at the collision point.</font>
00281 CVector2d proj= CVector2d(start) + CVector2d(delta)*<a class="code" href="driver__opengl__extension__def_8h.html#a384">t</a>;
00282 <font class="comment">// must add radius vector.</font>
00283 proj+= <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m3">Norm</a> * (sensSpeed?radius:-radius);
00284 <font class="comment">// compute projection on edge.</font>
00285 <font class="keywordtype">double</font> aProj= proj*<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m2">Dir</a>;
00286
00287 <font class="comment">// if on the interval of the edge.</font>
00288 <font class="keywordflow">if</font>( aProj>=<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m4">A0</a> && aProj<=<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m5">A1</a>)
00289 {
00290 <font class="comment">// collision occurs on interior of the edge. the normal to return is +- Norm.</font>
00291 <font class="keywordflow">if</font>(sensPos) <font class="comment">// if algebric distance of start position was >0.</font>
00292 normal= <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m3">Norm</a>;
00293 <font class="keywordflow">else</font>
00294 normal= -<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m3">Norm</a>;
00295
00296 <font class="comment">// return time of collision.</font>
00297 <font class="keywordflow">return</font> (float)<a class="code" href="driver__opengl__extension__def_8h.html#a384">t</a>;
00298 }
00299 }
00300 <font class="comment">// else, must test if circle collide segment at t=0. if yes, return 0.</font>
00301 <font class="comment">// ===============================</font>
00302 <font class="keywordflow">else</font>
00303 {
00304 <font class="comment">// There is just need to test if projection of circle's center onto the line hit the segment.</font>
00305 <font class="comment">// This is not a good test to know if a circle intersect a segment, but other cases are</font>
00306 <font class="comment">// managed with test of endPoints of the segment after.</font>
00307 <font class="keywordtype">float</font> aProj= start*<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m2">Dir</a>;
00308
00309 <font class="comment">// if on the interval of the edge.</font>
00310 <font class="keywordflow">if</font>( aProj>=<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m4">A0</a> && aProj<=<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m5">A1</a>)
00311 {
00312 <font class="comment">// if signs are equals, same side of the line, so we allow the circle to leave the edge.</font>
00313 <font class="comment">/* Special case: do not allow to leave the edge if we are too much in the edge.</font>
00314 <font class="comment"> It is important for CGlobalRetriever::testCollisionWithCollisionChains() because of the</font>
00315 <font class="comment"> "SURFACEMOVE NOT DETECTED" Problem.</font>
00316 <font class="comment"> Suppose we can walk on this chain SA/SB (separate Surface A/SurfaceB). Suppose we are near this edge, </font>
00317 <font class="comment"> and on Surface SA, and suppose there is an other chain SB/SC the circle collide with. If we </font>
00318 <font class="comment"> return 1 (no collision), SB/SC won't be detected (because only SA/?? chains will be tested) and </font>
00319 <font class="comment"> so the cylinder will penetrate SB/SC...</font>
00320 <font class="comment"> This case arise at best if chains SA/SB and chain SB/SC do an angle of 45�</font>
00321 <font class="comment"></font>
00322 <font class="comment"> \todo yoyo: this is a Hack.</font>
00323 <font class="comment"> */</font>
00324 <font class="keywordflow">if</font>(sensPos==sensSpeed && (-dist)<0.5*radius)
00325 {
00326 <font class="keywordflow">return</font> 1;
00327 }
00328 <font class="keywordflow">else</font>
00329 {
00330 <font class="comment">// hit the interior of the edge, and sensPos!=sensSpeed. So must stop now!!</font>
00331 <font class="comment">// collision occurs on interior of the edge. the normal to return is +- Norm.</font>
00332 <font class="keywordflow">if</font>(sensPos) <font class="comment">// if algebric distance of start position was >0.</font>
00333 normal= <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m3">Norm</a>;
00334 <font class="keywordflow">else</font>
00335 normal= -<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m3">Norm</a>;
00336
00337 <font class="keywordflow">return</font> 0;
00338 }
00339 }
00340 }
00341
00342 <font class="comment">// In this case, the Circle do not hit the edge on the interior, but may hit on borders.</font>
00343 <font class="comment">// ===============================</font>
00344 <font class="comment">// Then, we must compute collision sphere-points.</font>
00345 <font class="keywordtype">float</font> tmin, ttmp;
00346 <font class="comment">// first point.</font>
00347 tmin= <a class="code" href="namespaceNLPACS.html#a26">testCirclePoint</a>(start, delta, radius, <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>);
00348 <font class="comment">// second point.</font>
00349 ttmp= <a class="code" href="namespaceNLPACS.html#a26">testCirclePoint</a>(start, delta, radius, <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m1">P1</a>);
00350 tmin= <a class="code" href="bit__set_8cpp.html#a0">min</a>(tmin, ttmp);
00351
00352 <font class="comment">// if collision occurs, compute normal of collision.</font>
00353 <font class="keywordflow">if</font>(tmin<1)
00354 {
00355 <font class="comment">// to which point we collide?</font>
00356 CVector2f colPoint= tmin==ttmp? <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m1">P1</a> : <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>;
00357 <font class="comment">// compute position of the entity at collision.</font>
00358 CVector2f colPos= start + delta*tmin;
00359
00360 <font class="comment">// and so we have this normal (the perpendicular of the tangent at this point).</font>
00361 normal= colPos - colPoint;
00362 normal.normalize();
00363 }
00364
00365 <font class="keywordflow">return</font> tmin;
00366 }
00367
00368
00369
00370 <font class="comment">// ***************************************************************************</font>
<a name="l00371"></a><a class="code" href="classNLPACS_1_1CEdgeCollide.html#c0">00371</a> <font class="keywordtype">bool</font> CEdgeCollide::testEdgeMove(<font class="keyword">const</font> CVector2f &q0, <font class="keyword">const</font> CVector2f &q1, <font class="keyword">const</font> CVector2f &delta, <font class="keywordtype">float</font> &tMin, <font class="keywordtype">float</font> &tMax, <font class="keywordtype">bool</font> &normalOnBox)
00372 {
00373 <font class="keywordtype">double</font> a,b,cv,cc, d,e,f;
00374 CVector2d tmp;
00375
00376 <font class="comment">// compute D1 line equation of q0q1. bx - ay + c(t)=0, where c is function of time [0,1].</font>
00377 <font class="comment">// ===========================</font>
00378 tmp= q1 - q0; <font class="comment">// NB: along time, the direction doesn't change.</font>
00379 <font class="comment">// Divide by norm()�, so that a projection on this edge is true if the proj is in interval [0,1].</font>
00380 tmp/= tmp.sqrnorm();
00381 a= tmp.x;
00382 b= tmp.y;
00383 <font class="comment">// c= - q0(t)*CVector2d(b,-a). but since q0(t) is a function of time t (q0+delta*t), compute cv, and cc.</font>
00384 <font class="comment">// so c= cv*t + cc.</font>
00385 cv= - CVector2d(b,-a)*delta;
00386 cc= - CVector2d(b,-a)*q0;
00387
00388 <font class="comment">// compute D2 line equation of P0P1. ex - dy + f=0.</font>
00389 <font class="comment">// ===========================</font>
00390 tmp= <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m1">P1</a> - <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>;
00391 <font class="comment">// Divide by norm()�, so that a projection on this edge is true if the proj is in interval [0,1].</font>
00392 tmp/= tmp.sqrnorm();
00393 d= tmp.x;
00394 e= tmp.y;
00395 f= - CVector2d(e,-d)*<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>;
00396
00397
00398 <font class="comment">// Solve system.</font>
00399 <font class="comment">// ===========================</font>
00400 <font class="comment">/*</font>
00401 <font class="comment"> Compute the intersection I of 2 lines across time.</font>
00402 <font class="comment"> We have the system:</font>
00403 <font class="comment"> bx - ay + c(t)=0</font>
00404 <font class="comment"> ex - dy + f=0</font>
00405 <font class="comment"></font>
00406 <font class="comment"> which solve for:</font>
00407 <font class="comment"> det= ae-bd (0 <=> // lines)</font>
00408 <font class="comment"> x(t)= (d*c(t) - fa) / det</font>
00409 <font class="comment"> y(t)= (e*c(t) - fb) / det</font>
00410 <font class="comment"> */</font>
00411
00412 <font class="comment">// determinant of matrix2x2.</font>
00413 <font class="keywordtype">double</font> det= a*e - b*d;
00414 <font class="comment">// if to near of 0. (take delta for reference of test).</font>
00415 <font class="keywordflow">if</font>(det==0 || fabs(det)<delta.norm()*<a class="code" href="namespaceNLPACS.html#a6">EdgeCollideEpsilon</a>)
00416 <font class="keywordflow">return</font> <font class="keyword">false</font>;
00417
00418 <font class="comment">// intersection I(t)= pInt + vInt*t.</font>
00419 CVector2d pInt, vInt;
00420 pInt.x= ( d*cc - f*a ) / det;
00421 pInt.y= ( e*cc - f*b ) / det;
00422 vInt.x= ( d*cv ) / det;
00423 vInt.y= ( e*cv ) / det;
00424
00425
00426 <font class="comment">// Project Intersection.</font>
00427 <font class="comment">// ===========================</font>
00428 <font class="comment">/*</font>
00429 <font class="comment"> Now, we project x,y onto each line D1 and D2, which gives u(t) and v(t), each one giving the parameter of </font>
00430 <font class="comment"> the parametric line function. When it is in [0,1], we are on the edge.</font>
00431 <font class="comment"></font>
00432 <font class="comment"> u(t)= (I(t)-q0(t)) * CVector2d(a,b) = uc + uv*t</font>
00433 <font class="comment"> v(t)= (I(t)-P0) * CVector2d(d,e) = vc + vv*t</font>
00434 <font class="comment"> */</font>
00435 <font class="keywordtype">double</font> uc, uv;
00436 <font class="keywordtype">double</font> vc, vv;
00437 <font class="comment">// NB: q0(t)= q0+delta*t</font>
00438 uc= (pInt-q0) * CVector2d(a,b);
00439 uv= (vInt-delta) * CVector2d(a,b);
00440 vc= (pInt-<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>) * CVector2d(d,e);
00441 vv= (vInt) * CVector2d(d,e);
00442
00443
00444 <font class="comment">// Compute intervals.</font>
00445 <font class="comment">// ===========================</font>
00446 <font class="comment">/*</font>
00447 <font class="comment"> Now, for each edge, compute time interval where parameter is in [0,1]. If intervals overlap, there is a collision.</font>
00448 <font class="comment"> */</font>
00449 <font class="keywordtype">double</font> tu0, tu1, tv0, tv1;
00450 <font class="comment">// infinite interval.</font>
00451 <font class="keywordtype">bool</font> allU=<font class="keyword">false</font>, allV=<font class="keyword">false</font>;
00452
00453 <font class="comment">// compute time interval for u(t).</font>
00454 <font class="keywordflow">if</font>(uv==0 || fabs(uv)<<a class="code" href="namespaceNLPACS.html#a6">EdgeCollideEpsilon</a>)
00455 {
00456 <font class="comment">// The intersection does not move along D1. Always projected on u(t)=uc. so if in [0,1], OK, else never collide.</font>
00457 <font class="keywordflow">if</font>(uc<0 || uc>1)
00458 <font class="keywordflow">return</font> <font class="keyword">false</font>;
00459 <font class="comment">// else suppose "always valid".</font>
00460 tu0 =tu1= 0;
00461 allU= <font class="keyword">true</font>;
00462 }
00463 <font class="keywordflow">else</font>
00464 {
00465 tu0= (0-uc)/uv; <font class="comment">// t for u(t)=0</font>
00466 tu1= (1-uc)/uv; <font class="comment">// t for u(t)=1</font>
00467 }
00468
00469 <font class="comment">// compute time interval for v(t).</font>
00470 <font class="keywordflow">if</font>(vv==0 || fabs(vv)<<a class="code" href="namespaceNLPACS.html#a6">EdgeCollideEpsilon</a>)
00471 {
00472 <font class="comment">// The intersection does not move along D2. Always projected on v(t)=vc. so if in [0,1], OK, else never collide.</font>
00473 <font class="keywordflow">if</font>(vc<0 || vc>1)
00474 <font class="keywordflow">return</font> <font class="keyword">false</font>;
00475 <font class="comment">// else suppose "always valid".</font>
00476 tv0 =tv1= 0;
00477 allV= <font class="keyword">true</font>;
00478 }
00479 <font class="keywordflow">else</font>
00480 {
00481 tv0= (0-vc)/vv; <font class="comment">// t for v(t)=0</font>
00482 tv1= (1-vc)/vv; <font class="comment">// t for v(t)=1</font>
00483 }
00484
00485
00486 <font class="comment">// clip intervals.</font>
00487 <font class="comment">// ===========================</font>
00488 <font class="comment">// order time interval.</font>
00489 <font class="keywordflow">if</font>(tu0>tu1)
00490 swap(tu0, tu1); <font class="comment">// now, [tu0, tu1] represent the time interval where line D2 hit the edge D1.</font>
00491 <font class="keywordflow">if</font>(tv0>tv1)
00492 swap(tv0, tv1); <font class="comment">// now, [tv0, tv1] represent the time interval where line D1 hit the edge D2.</font>
00493
00494 normalOnBox= <font class="keyword">false</font>;
00495 <font class="keywordflow">if</font>(!allU && !allV)
00496 {
00497 <font class="comment">// if intervals do not overlap, no collision.</font>
00498 <font class="keywordflow">if</font>(tu0>tv1 || tv0>tu1)
00499 <font class="keywordflow">return</font> <font class="keyword">false</font>;
00500 <font class="keywordflow">else</font>
00501 {
00502 <font class="comment">// compute intersection of intervals.</font>
00503 tMin= (float)max(tu0, tv0);
00504 tMax= (float)<a class="code" href="bit__set_8cpp.html#a0">min</a>(tu1, tv1);
00505 <font class="comment">// if collision of edgeCollide against the bbox.</font>
00506 <font class="keywordflow">if</font>(tv0>tu0)
00507 normalOnBox= <font class="keyword">true</font>;
00508 }
00509 }
00510 <font class="keywordflow">else</font> <font class="keywordflow">if</font>(allU)
00511 {
00512 <font class="comment">// intersection of Infinite and V interval.</font>
00513 tMin= (float)tv0;
00514 tMax= (float)tv1;
00515 <font class="comment">// if collision of edgeCollide against the bbox.</font>
00516 normalOnBox= <font class="keyword">true</font>;
00517 }
00518 <font class="keywordflow">else</font> <font class="keywordflow">if</font>(allV)
00519 {
00520 <font class="comment">// intersection of Infinite and U interval.</font>
00521 tMin= (float)tu0;
00522 tMax= (float)tu1;
00523 }
00524 <font class="keywordflow">else</font>
00525 {
00526 <font class="comment">// if allU && allV, this means delta is near 0, and so there is always collision.</font>
00527 tMin= -1000;
00528 tMax= 1000;
00529 }
00530
00531 <font class="keywordflow">return</font> <font class="keyword">true</font>;
00532 }
00533
00534
00535 <font class="comment">// ***************************************************************************</font>
<a name="l00536"></a><a class="code" href="classNLPACS_1_1CEdgeCollide.html#a3">00536</a> <font class="keywordtype">float</font> CEdgeCollide::testBBoxMove(<font class="keyword">const</font> CVector2f &start, <font class="keyword">const</font> CVector2f &delta, <font class="keyword">const</font> CVector2f bbox[4], CVector2f &normal)
00537 {
00538 <font class="comment">// distance from center to line.</font>
00539 <font class="keywordtype">float</font> dist= start*<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m3">Norm</a> + <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m6">C</a>;
00540
00541 <font class="comment">// test if the movement is against the line or not.</font>
00542 <font class="keywordtype">bool</font> sensPos= dist>0;
00543 <font class="comment">// if signs are equals, same side of the line, so we allow the circle to leave the line.</font>
00544 <font class="comment">/*if(sensPos==sensSpeed)</font>
00545 <font class="comment"> return 1;*/</font>
00546
00547
00548 <font class="comment">// Else, do 4 test edge/edge, and return Tmin.</font>
00549 <font class="keywordtype">float</font> tMin, tMax;
00550 <font class="keywordtype">bool</font> edgeCollided= <font class="keyword">false</font>;
00551 <font class="keywordtype">bool</font> normalOnBox= <font class="keyword">false</font>;
00552 CVector2f boxNormal;
00553 <font class="keywordflow">for</font>(sint i=0;i<4;i++)
00554 {
00555 <font class="keywordtype">float</font> t0, t1;
00556 <font class="keywordtype">bool</font> nob;
00557 CVector2f a= bbox[i];
00558 CVector2f b= bbox[(i+1)&3];
00559
00560 <font class="comment">// test move against this edge.</font>
00561 <font class="keywordflow">if</font>(<a class="code" href="classNLPACS_1_1CEdgeCollide.html#c0">testEdgeMove</a>(a, b, delta, t0, t1, nob))
00562 {
00563 <font class="keywordflow">if</font>(edgeCollided)
00564 {
00565 tMin= <a class="code" href="bit__set_8cpp.html#a0">min</a>(t0, tMin);
00566 tMax= max(t1, tMax);
00567 }
00568 <font class="keywordflow">else</font>
00569 {
00570 edgeCollided= <font class="keyword">true</font>;
00571 tMin= t0;
00572 tMax= t1;
00573 }
00574
00575 <font class="comment">// get normal of box against we collide.</font>
00576 <font class="keywordflow">if</font>(tMin==t0)
00577 {
00578 normalOnBox= nob;
00579 <font class="keywordflow">if</font>(nob)
00580 {
00581 CVector2f dab;
00582 <font class="comment">// bbox must be CCW.</font>
00583 dab= b-a;
00584 <font class="comment">// the normal is computed so that the vector goes In the bbox.</font>
00585 boxNormal.x= -dab.y;
00586 boxNormal.y= dab.x;
00587 }
00588 }
00589 }
00590 }
00591
00592 <font class="comment">// if collision occurs,and int the [0,1] interval...</font>
00593 <font class="keywordflow">if</font>(edgeCollided && tMin<1 && tMax>0)
00594 {
00595 <font class="comment">// compute normal of collision.</font>
00596 <font class="keywordflow">if</font>(normalOnBox)
00597 {
00598 <font class="comment">// assume collsion is an endpoint of the edge against the bbox.</font>
00599 normal= boxNormal;
00600 }
00601 <font class="keywordflow">else</font>
00602 {
00603 <font class="comment">// assume collision occurs on interior of the edge. the normal to return is +- Norm.</font>
00604 <font class="keywordflow">if</font>(sensPos) <font class="comment">// if algebric distance of start position was >0.</font>
00605 normal= <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m3">Norm</a>;
00606 <font class="keywordflow">else</font>
00607 normal= -<a class="code" href="classNLPACS_1_1CEdgeCollide.html#m3">Norm</a>;
00608 }
00609
00610 <font class="comment">// compute time of collison.</font>
00611 <font class="keywordflow">if</font>(tMin>0)
00612 <font class="comment">// return time of collision.</font>
00613 <font class="keywordflow">return</font> tMin;
00614 <font class="keywordflow">else</font>
00615 {
00616 <font class="comment">// The bbox is inside the edge, at t==0. test if it goes out or not.</font>
00617 <font class="comment">// accept only if we are much near the exit than the enter.</font>
00618 <font class="comment">/* NB: 0.2 is an empirical value "which works well". Normally, 1 is the good value, but because of the</font>
00619 <font class="comment"> "SURFACEMOVE NOT DETECTED" Problem (see testCircleMove()), we must be more restrictive.</font>
00620 <font class="comment"> */</font>
00621 <font class="keywordflow">if</font>( tMax<0.2*(-tMin) )
00622 <font class="keywordflow">return</font> 1;
00623 <font class="keywordflow">else</font>
00624 <font class="keywordflow">return</font> 0;
00625 }
00626 }
00627 <font class="keywordflow">else</font>
00628 <font class="keywordflow">return</font> 1;
00629
00630 }
00631
00632
00633 <font class="comment">// ***************************************************************************</font>
<a name="l00634"></a><a class="code" href="classNLPACS_1_1CEdgeCollide.html#a4">00634</a> <font class="keywordtype">bool</font> CEdgeCollide::testBBoxCollide(<font class="keyword">const</font> CVector2f bbox[4])
00635 {
00636 <font class="comment">// clip the edge against the edge of the bbox.</font>
00637 CVector2f p0= <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m0">P0</a>, p1= <a class="code" href="classNLPACS_1_1CEdgeCollide.html#m1">P1</a>;
00638
00639 <font class="keywordflow">for</font>(sint i=0; i<4; i++)
00640 {
00641 CVector2f a= bbox[i];
00642 CVector2f b= bbox[(i+1)&3];
00643 CVector2f delta= b-a, norm;
00644 <font class="comment">// sign is important. bbox is CCW. normal goes OUT the bbox.</font>
00645 norm.x= delta.y;
00646 norm.y= -delta.x;
00647
00648 <font class="keywordtype">float</font> d0= (p0-a)*norm;
00649 <font class="keywordtype">float</font> d1= (p1-a)*norm;
00650
00651 <font class="comment">// if boths points are out this plane, no collision.</font>
00652 <font class="keywordflow">if</font>( d0>0 && d1>0)
00653 <font class="keywordflow">return</font> <font class="keyword">false</font>;
00654 <font class="comment">// if difference, must clip.</font>
00655 <font class="keywordflow">if</font>( d0>0 || d1>0)
00656 {
00657 CVector2f intersect= p0 + (p1-p0)* ((0-d0)/(d1-d0));
00658 <font class="keywordflow">if</font>(d1>0)
00659 p1= intersect;
00660 <font class="keywordflow">else</font>
00661 p0= intersect;
00662 }
00663 }
00664
00665 <font class="comment">// if a segment is still in the bbox, collision occurs.</font>
00666 <font class="keywordflow">return</font> <font class="keyword">true</font>;
00667 }
00668
00669
00670
00671 } <font class="comment">// NLPACS</font>
</pre></div>
<!-- footer -->
<BR><FONT Size=+5> </FONT>
</TD>
<TD WIDTH=15><IMG SRC=http://www.nevrax.org/inc/img/pixel.gif WIDTH=15 HEIGHT=15 BORDER=0 ALT=""></TD>
</TR>
</TABLE>
</BODY>
</HTML>
|
