-
Notifications
You must be signed in to change notification settings - Fork 29
/
Copy pathintersections.html
407 lines (349 loc) · 60.5 KB
/
intersections.html
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
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>Object/Object Intersection</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
<link rel="shortcut icon" href="favicon.ico" type="image/x-icon"/>
<link rel="icon" href="favicon.ico" type="image/x-icon"/>
<link rel="stylesheet" href="rtr4.css" type="text/css"/>
</head>
<body>
<div id="wrapper">
<div id="header">
<div id="rtr3-header-image">
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<tr bgcolor="#10304B">
<td>
<a href="http://www.realtimerendering.com/blog/">
<img src="rtr-header.png" alt="Header image" width="410" height="106"/>
</a>
</td>
</tr>
</table>
</div>
<div id="navigation" class="clearfix">
<ul class="primary">
<li><a href="http://www.realtimerendering.com/blog/" rel="home">Blog</a></li>
<li><a title="Recommended books" href="books.html">Graphics books</a></li>
<li><a class="nav-current" title="Object / object intersection page" href="intersections.html">Intersections</a></li>
<li><a title="Sites we like" href="portal.html">Portal</a></li>
<li><a title="Ray Tracing Resources" href="raytracing.html">Ray tracing</a></li>
<li><a title="Main resources page" href="index.html">Resources</a></li>
<li><a title="USD and glTF Resources" href="usd_gltf.html">USD & glTF</a></li>
<li><a title="WebGL/three.js Resources" href="webgl.html">WebGL</a></li>
</ul>
</div>
</div>
<div id="content" class="clearfix">
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<tr>
<td class="pageName">Ray Tracing Resources Page</td>
</tr>
<tr>
<td valign="top"><img src="spacer.gif" alt="" height="6" border="0"/><br/>
</tr>
<tr>
<td class="bodyText">
<div class="metadata">
Last changed: January 21, 2025
</div>
<P>
This page gives a grid of intersection routines for various popular objects, pointing to resources
in books and on the web. The most comprehensive books on the subject are
<a href="https://www.geometrictools.com/Books/Books.html"><I>Geometric Tools for Computer Graphics</I></a> (GTCG) and
<a href="http://realtimecollisiondetection.net/"><I>Real-Time Collision Detection</I></a> (RTCD);
the former is all-encompassing, the latter more approachable and focused.
A book focused in large part on object/object intersection tests is the
<I><a href="https://www.packtpub.com/product/game-physics-cookbook/9781787123663">Game Physics Cookbook</a></I> (GPC),
with <a href="https://github.com/gszauer/GamePhysicsCookbook">code</a> -
see its <a href="https://github.com/gszauer/GamePhysicsCookbook#collision-detection">giant grid</a> for what intersections it covers.
<a href="https://www.iquilezles.org/www/articles/intersectors/intersectors.htm">Quílez</a> has a bunch of shader-based ray/object intersectors, including ones (beyond those listed in the table) for the torus, disk, and capsule.
<P>
Guide to source abbreviations:
<UL>
<LI><B>3DG</B> - <a href="https://smile.amazon.com/exec/obidos/ASIN/0201619210?tag=realtimerenderin"><I>3D Games: Real-time Rendering and Software Technology</I></a>, Alan Watt and Fabio Policarpo, Addison-Wesley, 2001.
<LI><B>GPC</B> - <I><a href="https://www.packtpub.com/product/game-physics-cookbook/9781787123663">Game Physics Cookbook</a></I>, by Gabor Szauer, Packt Publishing, March 2017, with <a href="https://github.com/gszauer/GamePhysicsCookbook">code</a>
<LI><B>GPG</B> - <a href="https://smile.amazon.com/exec/obidos/ASIN/1584500492?tag=realtimerenderin"><I>Game Programming Gems</I></a>, ed. Mark DeLoura, Charles River Media, 2000.
<LI><B>GTCG</B> - <a href="https://www.geometrictools.com/Books/Books.html"><I>Geometric Tools for Computer Graphics</I></a>, Philip J. Schneider and David H. Eberly, Morgan Kaufmann Publishers, 2002. Good, comprehensive book on this topic.
<LI><B>Gems</B> - <a href="http://www.graphicsgems.org">The <I>Graphics Gems</I> series</a>. See the book's <a href="http://www.graphicsgems.org">website</a> for individual book links and code.
<LI><B>GTweb</B> - <a href="https://www.geometrictools.com/">Geometric Tools</a>, Dave Eberly's online computer graphics related software repository. His book <a href="https://www.geometrictools.com/Books/Books.html"><I>3D Game Engine Design</I></a> also covers these, in a readable format, as well as many other <a href="https://www.geometrictools.com/Samples/Geometrics.html">object/object intersection tests</a>.
<LI><B>IRT</B> - <a href="https://smile.amazon.com/exec/obidos/ASIN/0122861604?tag=realtimerenderin"><I>An Introduction to Ray Tracing</I></a>, ed. Andrew Glassner, Academic Press, 1989. <a href="http://www.realtimerendering.com/blog/an-introduction-to-ray-tracing-is-now-free-for-download/">Free to download</a>.
<LI><B>JCGT</B> - <a href="http://jcgt.org/"><I>The Journal of Computer Graphics Techniques</I></a>.
<LI><B>jgt</B> - <a href="https://www.tandfonline.com/toc/ujgt21/current"><I>journal of graphics tools</I></a>. A partial <a href="https://github.com/erich666/jgt-code">code repository</a> is available.
<LI><B>RTCD</B> - <a href="http://realtimecollisiondetection.net/"><I>Real-Time Collision Detection</I></a>, by Christer Ericson, Morgan Kaufmann Publishers, 2004.
<LI><B>RTR4</B> - <a href="http://www.realtimerendering.com/"><I>Real-Time Rendering, Fourth Edition</I></a>, by <a href="https://cs.lth.se/tomas-akenine-moller/">Tomas Möller</a>, <a href="http://erichaines.com">Eric Haines</a>, Naty Hoffman, Angelo Pesce, Michał Iwanicki, and Sébastien Hillaire <a href="https://www.routledge.com/">A.K. Peters/CRC Press</a>, 2018.
<LI><B>SG</B> - <a href="http://plib.sourceforge.net/sg/index.html">Simple Geometry library</a>, Steve Baker's vector, matrix, and quaternion manipulation library.
<LI><B>Shadertoy</B> - <a href="https://www.iquilezles.org/www/articles/intersectors/intersectors.htm">Quílez</a> gives code snippets and shader-based demos, runnable in your browser (best on Chrome).
<LI><B>TgS</B> - <a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">Teikitu gaming System COLLISION</a>, Andrew Aye's object/object intersection/distance and sweep/penetration software (non-commercial use only).
<LI><B>TVCG</B> - <a href="https://www.computer.org/csdl/journal/tg">IEEE Transactions on Visualization and Computer Graphics</a>.
</UL>
<P>
Individual article references follow after the table.
<P>
<H2>Static Object Intersections</H2>
Entries are listed from oldest to newest, so often the <i>last</i> entry is the best. This table covers objects not moving; see the next section for dynamic objects.
<P>
<div id="intersect-table">
<table BORDER=1 CELLSPACING=1 CELLPADDING=2 >
<tr>
<td> </td>
<td ALIGN="CENTER"><B>ray</B></td>
<td ALIGN="CENTER"><B>plane</B></td>
<td ALIGN="CENTER"><B>sphere</B></td>
<td ALIGN="CENTER"><B>cylinder</B></td>
<td ALIGN="CENTER"><B>cone</B></td>
<td ALIGN="CENTER"><B>triangle</B></td>
<td ALIGN="CENTER"><B>AABB</B></td>
<td ALIGN="CENTER"><B>OBB</B></td>
<td ALIGN="CENTER"><B>frustum</B></td>
<td ALIGN="CENTER"><B>polyhedron</B></td>
<td> </td>
</tr>
<tr>
<td ALIGN="LEFT"><B>ray</B></td>
<td ALIGN="CENTER"><a href="#I304">Gems p.304</a>;<BR><a href="http://plib.sourceforge.net/sg/index.html">SG</a>;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.198;<BR><a href="https://web.archive.org/web/20110716101931/http://www.softsurfer.com/Archive/algorithm_0104/algorithm_0104B.htm">SoftSurfer</a>: <a href="http://geomalgorithms.com/code.html">code</a>;<BR>RTR4 p.989</td>
<td ALIGN="CENTER"><a href="http://www.siggraph.org/education/materials/HyperGraph/raytrace/rayplane_intersection.htm">IRT p.50</a>,88;<BR><a href="http://plib.sourceforge.net/sg/index.html">SG</a>;<BR>GTCG p.482;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.175;<BR><a href="https://web.archive.org/web/20110716101931/http://www.softsurfer.com/Archive/algorithm_0104/algorithm_0104B.htm">SoftSurfer</a> (<a href="https://web.archive.org/web/20110716101940/http://www.softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm">more</a>): <a href="http://geomalgorithms.com/code.html">code</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR><a href="http://graphicscodex.com">Graphics Codex</a></td>
<td ALIGN="CENTER"><a href="http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter1.htm">IRT p.39</a>,91;<BR><a href="#I388">Gems p.388</a>;<BR><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9172&rep=rep1&type=pdf">Held jgt 2(4)</a>;<BR><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR>3DG p.16;<BR>GTCG p.501;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.127,177;<BR><a href="http://graphicscodex.com">Graphics Codex</a>;<BR>RTR4 p.955;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR><a href="http://www.iquilezles.org/www/articles/intersectors/intersectors.htm">Shadertoy</a> <a href="https://www.shadertoy.com/view/4d2XWV">(demo)</a></td>
<td ALIGN="CENTER">IRT p.91;<BR><a href="#IV357">Gems IV p.356</a>;<BR><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9172&rep=rep1&type=pdf">Held jgt 2(4)</a>;<BR><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR>GTCG p.507;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.194;<BR><a href="http://www.iquilezles.org/www/articles/intersectors/intersectors.htm">Shadertoy</a> <a href="https://www.shadertoy.com/view/4lcSRn">(demo)</a></td>
<td ALIGN="CENTER">IRT p.91;<BR><a href="#V227">Gems V p.227</a>;<BR><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9172&rep=rep1&type=pdf">Held jgt 2(4)</a>;<BR><a href="https://www.geometrictools.com/Documentation/IntersectionLineCone.pdf">GTweb doc</a>;<BR>GTCG p.512</td>
<td ALIGN="CENTER"><a href="https://www.tandfonline.com/doi/abs/10.1080/10867651.1997.10487468">Möller-Trumbore jgt 2(1)</a>: <a href="https://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/">code</a> (<a href="https://github.com/erich666/jgt-code/tree/master/Volume_02/Number_1/Moller1997a">mirror</a>), <a href="http://www.graphics.cornell.edu/pubs/1997/MT97.html">paper draft</a>;<BR><a href="http://www.siggraph.org/education/materials/HyperGraph/raytrace/raypolygon_intersection.htm">IRT p.53</a>,102;<BR><a href="#IV24">Gems IV p.24</a>;<BR><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9172&rep=rep1&type=pdf">Held jgt 2(4)</a>;<BR><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR>3DG p.17;<BR><a href="https://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/">Möller</a> (<a href="https://github.com/erich666/jgt-code/tree/master/Volume_02/Number_1/Moller1997a">mirror</a>);<BR>GTCG p.485;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.153,184;<BR><a href="https://www.tandfonline.com/doi/abs/10.1080/2151237X.2005.10129195">Löfstedt jgt 10(2)</a>: <a href="https://github.com/erich666/jgt-code/tree/master/Volume_10/Number_2/Lofstedt2005">code</a>, <a href="https://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/pubs/ray_tri_survey.pdf">paper draft</a><BR><a href="https://www.tandfonline.com/doi/abs/10.1080/2151237X.2005.10129201">Chirkov jgt 10(3)</a>: <a href="https://github.com/erich666/jgt-code/tree/master/Volume_10/Number_3/Chirkov2005">code</a>;<BR><a href="https://www.tandfonline.com/doi/abs/10.1080/2151237X.2005.10129208">Lagae jgt 10(4)</a>: <a href="https://github.com/erich666/jgt-code/tree/master/Volume_10/Number_4/Lagae2005">code</a>, <a href="https://web.archive.org/web/20120905133158/http://people.cs.kuleuven.be/~ares.lagae/publications/LD05ERQIT/LD05ERQIT.pdf">paper draft</a>;<BR><a href="https://web.archive.org/web/20110716101940/http://www.softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm">SoftSurfer</a>: <a href="http://geomalgorithms.com/code.html">code</a>;<BR><a href="https://www.computer.org/csdl/journal/tg/2010/03/ttg2010030434/13rRUyp7tWT ">Havel TVCG June 2009</a>;<BR><a href="http://jcgt.org/published/0002/01/05/">Woop JCGT 2(1)</a>;<BR><a href="http://jcgt.org/published/0005/03/03/">Baldwin JCGT 5(3)</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR><a href="http://graphicscodex.com/Sample2-RayTriangleIntersection.pdf">Graphics Codex</a>;<BR>RTR4 p.962;<BR><a href="http://www.iquilezles.org/www/articles/intersectors/intersectors.htm">Shadertoy</a> <a href="https://www.shadertoy.com/view/MlGcDz">(demo)</a></td>
<td ALIGN="CENTER"><a href="http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter3.htm">IRT p.65</a>,104;<BR><a href="#I395">Gems p.395</a>;<BR><a href="https://dl.acm.org/doi/abs/10.1145/1198555.1198745">Smits</a>;<BR>3DG p.20;<BR><a href="http://www.codercorner.com/RayAABB.cpp">Terdiman (optimized Woo)</a>;<BR>Schroeder;<BR>GTCG p.626;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.179;<BR><a href="https://github.com/erich666/jgt-code/tree/master/Volume_09/Number_1/Mahovsky2004">Mahovsky jgt 9(1)</a>;<BR><a href="https://github.com/erich666/jgt-code/tree/master/Volume_10/Number_1/Williams2005">Williams jgt 10(1)</a> (<a href="https://dl.acm.org/doi/abs/10.1145/1198555.1198748">code</a>);<BR><a href="https://www.cg.cs.tu-bs.de/people/eisemann">Eisemann jgt 12(4)</a> (<a href="https://web.archive.org/web/20150910070400/https://www.cg.cs.tu-bs.de/media/publications/fast-rayaxis-aligned-bounding-box-overlap-tests-using-ray-slopes.pdf">code</a>);<BR><a href="http://psgraphics.blogspot.com/2016/02/new-simple-ray-box-test-from-andrew.html">Shirley 2016</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR><a href="https://github.com/constantinides/RAABB">Chatzianastasiou</a>;<BR><a href="http://jcgt.org/published/0007/03/04/">Majercik JCGT 7(3)</a>;<BR>RTR4 p.959;<BR><a href="https://medium.com/@bromanz/another-view-on-the-classic-ray-aabb-intersection-algorithm-for-bvh-traversal-41125138b525">Wiche</a>;<BR><a href="http://www.iquilezles.org/www/articles/intersectors/intersectors.htm">Shadertoy</a> <a href="https://www.shadertoy.com/view/ld23DV">(demo)</a></td>
<td ALIGN="CENTER">(IRT p.104;<BR><a href="#II247">Gems II p.247</a>);<BR><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://web.archive.org/web/19991129050752/http://www.gamasutra.com/features/19991018/Gomez_6.htm">Gomez</a>;<BR>GTCG p.630;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.179;<BR><a href="http://www.iquilezles.org/www/articles/intersectors/intersectors.htm">Shadertoy</a> <a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR>RTR4 p.960;<BR><a href="https://www.shadertoy.com/view/ld23DV">(demo)</a></td>
<td ALIGN="CENTER">(IRT p.104;<BR><a href="#II247">Gems II p.247</a>)</td>
<td ALIGN="CENTER">IRT p.104;<BR><a href="#II247">Gems II p.247</a>;<BR>GTCG p.493;<BR><a href="https://github.com/erich666/jgt-code/tree/master/Volume_08/Number_4/Platis2003">Platis jgt 8(4)</a>;<BR>RTCD p.198;<BR><a href="https://web.archive.org/web/20110725233122/http://www.softsurfer.com/Archive/algorithm_0111/algorithm_0111.htm">SoftSurfer</a>: <a href="http://geomalgorithms.com/code.html">code</a></td>
<td ALIGN="LEFT"><B>ray</B></td>
</tr>
<tr>
<td ALIGN="LEFT"><B>plane</B></td>
<td ALIGN="CENTER"><a href="http://www.siggraph.org/education/materials/HyperGraph/raytrace/rayplane_intersection.htm">IRT p.50</a>,88;<BR><a href="http://plib.sourceforge.net/sg/index.html">SG</a>;<BR>GTCG p.482;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.175;<BR><a href="https://web.archive.org/web/20110716101931/http://www.softsurfer.com/Archive/algorithm_0104/algorithm_0104B.htm">SoftSurfer</a> (<a href="https://web.archive.org/web/20110716101940/http://www.softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm">more</a>): <a href="http://geomalgorithms.com/code.html">code</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR><a href="http://graphicscodex.com">Graphics Codex</a></td>
<td ALIGN="CENTER"><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="http://plib.sourceforge.net/sg/index.html">SG</a>;<BR>GTCG p.529;<BR>RTCD p.207;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a></td>
<td ALIGN="CENTER">distance of<BR>center to plane<BR><= radius;<BR><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://web.archive.org/web/19991128214140/http://www.gamasutra.com/features/19991018/Gomez_1.htm">Gomez</a>;<BR>GTCG p.548;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.160,219;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a></td>
<td ALIGN="CENTER"><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR>GTCG p.551;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR><a href="https://www.geometrictools.com/Documentation/IntersectionCylinderPlane.pdf">GTweb doc</a></td>
<td ALIGN="CENTER">GTCG p.563;<BR>RTCD p.164</td>
<td ALIGN="CENTER">Check if all<BR>vertices are<BR>on one side;(<a href="https://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/tritri_tam.pdf">Möller jgt 2(2)</a>);<BR>GTCG p.534;<BR><a href="https://web.archive.org/web/20110716101940/http://www.softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm">SoftSurfer</a>: <a href="http://geomalgorithms.com/code.html">code</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a></td>
<td ALIGN="CENTER"><a href="#IV74">Gems IV p.74</a>;<BR>GTCG p.634;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.161,222;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR>RTR4 p.970</td>
<td ALIGN="CENTER"><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://web.archive.org/web/19991127082151/http://www.gamasutra.com/features/19991018/Gomez_7.htm">Gomez</a>;<BR>GTCG p.635;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.161;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR>RTR4 p.972</td>
<td ALIGN="CENTER"> </td>
<td ALIGN="CENTER"> </td>
<td ALIGN="LEFT"><B>plane</B></td>
</tr>
<tr>
<td ALIGN="LEFT"><B>sphere</B></td>
<td ALIGN="CENTER"><a href="http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter1.htm">IRT p.39</a>,91;<BR><a href="#I388">Gems p.388</a>;<BR><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9172&rep=rep1&type=pdf">Held jgt 2(4)</a>;<BR><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR>3DG p.16;<BR>GTCG p.501;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.127,177;<BR><a href="http://graphicscodex.com">Graphics Codex</a>;<BR>RTR4 p.955;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR><a href="http://www.iquilezles.org/www/articles/intersectors/intersectors.htm">Shadertoy</a> <a href="https://www.shadertoy.com/view/4d2XWV">(demo)</a></td>
<td ALIGN="CENTER">distance of<BR>center to plane<BR><= radius;<BR><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://web.archive.org/web/19991128214140/http://www.gamasutra.com/features/19991018/Gomez_1.htm">Gomez</a>;<BR>GTCG p.548;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.160,219;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a></td>
<td ALIGN="CENTER">If radii A+B >=<BR>center/center distance;<BR><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9172&rep=rep1&type=pdf">Held jgt 2(4)</a>;<BR><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://web.archive.org/web/19991128214140/http://www.gamasutra.com/features/19991018/Gomez_1.htm">Gomez</a>;<BR>GPG p.390;<BR>GTCG p.602;<BR><a https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.88,215,223;<BR>Ellipsoids: <a href="https://www.geometrictools.com/Documentation/IntersectionOfEllipsoids.pdf">GTweb doc</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR>RTR4 p.976</td>
<td ALIGN="CENTER">If radii A+B >=<BR>center/axis distance;<BR><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9172&rep=rep1&type=pdf">Held jgt 2(4)</a>;<BR>(GTCG p.602);<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.114</td>
<td ALIGN="CENTER"><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://www.geometrictools.com/Documentation/IntersectionSphereCone.pdf">GTweb doc</a>;<BR>(GTCG p.602);<BR><a href="https://blog.squareys.de/sphere-cone-intersection/">Hale</a></td>
<td ALIGN="CENTER"><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9172&rep=rep1&type=pdf">Held jgt 2(4)</a>;<BR><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://www.tandfonline.com/doi/abs/10.1080/10867651.1999.10487499">Karabassi jgt 4(1)</a>;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.135,167,226;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a></td>
<td ALIGN="CENTER"><a href="#I335">Gems p.335</a>;<BR><a href="https://web.archive.org/web/19991129023147/http://www.gamasutra.com/features/19991018/Gomez_4.htm">Gomez</a>;<BR>GTCG p.644;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.130,165,228;<BR>Ellipsoid: <a href="https://www.geometrictools.com/Documentation/IntersectionBoxEllipsoid.pdf">GTweb doc</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR>RTR4 p.977</td>
<td ALIGN="CENTER"><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.132,166<BR><a href="https://www.semanticscholar.org/paper/An-Efficient-Ellipsoid-OBB-Intersection-Test-Larsson/0af6971bb3fc403cdd27e32d81d78497fc57b574?p2df">Larsson</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a></td>
<td ALIGN="CENTER"><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="http://www.cse.chalmers.se/~uffe/">Assarsson</a>;<BR>GPG p.433;<BR>3DG p.302;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR>RTR4 p.984</td>
<td ALIGN="CENTER">3DG p.462;<BR>RTCD p.142</td>
<td ALIGN="LEFT"><B>sphere</B></td>
</tr>
<tr>
<td ALIGN="LEFT"><B>(capped) cylinder</B></td>
<td ALIGN="CENTER">IRT p.91;<BR><a href="#IV357">Gems IV p.356</a>;<BR><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9172&rep=rep1&type=pdf">Held jgt 2(4)</a>;<BR><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR>GTCG p.507;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.194;<BR><a href="http://www.iquilezles.org/www/articles/intersectors/intersectors.htm">Shadertoy</a> <a href="https://www.shadertoy.com/view/4lcSRn">(demo)</a></td>
<td ALIGN="CENTER"><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR>GTCG p.551;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR><a href="https://www.geometrictools.com/Documentation/IntersectionCylinderPlane.pdf">GTweb doc</a></td>
<td ALIGN="CENTER">If radii A+B >=<BR>center/axis distance;<BR><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9172&rep=rep1&type=pdf">Held jgt 2(4)</a>;<BR>(GTCG p.602);<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.114</td>
<td ALIGN="CENTER">If radii A+B >=<BR>axis/axis distance;<BR><a href="https://www.geometrictools.com/Documentation/IntersectionOfCylinders.pdf">GTweb doc</a>;<BR><a href="https://www.geometrictools.com/Documentation/IntersectionInfiniteCylinders.pdf">GTweb doc</a>;<BR>GTCG p.602,646;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.114</td>
<td ALIGN="CENTER">(GTCG p.602)</td>
<td ALIGN="CENTER"><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9172&rep=rep1&type=pdf">Held jgt 2(4)</a>;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR><a href="https://www.geometrictools.com/Documentation/IntersectionTriangleCylinder.pdf">GTweb doc</a></td>
<td ALIGN="CENTER"></td>
<td ALIGN="CENTER"></td>
<td ALIGN="CENTER">GPG p.380</td>
<td ALIGN="CENTER"> </td>
<td ALIGN="LEFT"><B>(capped) cylinder</B></td>
</tr>
<tr>
<td ALIGN="LEFT"><B>(capped) cone</B></td>
<td ALIGN="CENTER">IRT p.91;<BR><a href="#V227">Gems V p.227</a>;<BR><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9172&rep=rep1&type=pdf">Held jgt 2(4)</a>;<BR><a href="https://www.geometrictools.com/Documentation/IntersectionLineCone.pdf">GTweb doc</a>;<BR>GTCG p.512</td>
<td ALIGN="CENTER">GTCG p.563;<BR>RTCD p.164</td>
<td ALIGN="CENTER"><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://www.geometrictools.com/Documentation/IntersectionSphereCone.pdf">GTweb doc</a>;<BR>(GTCG p.602);<BR><a href="https://blog.squareys.de/sphere-cone-intersection/">Hale</a></td>
<td ALIGN="CENTER">(GTCG p.602)</td>
<td ALIGN="CENTER">(GTCG p.602)</td>
<td ALIGN="CENTER"><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9172&rep=rep1&type=pdf">Held jgt 2(4)</a>;<BR><a href="https://www.geometrictools.com/Documentation/IntersectionTriangleCone.pdf">GTweb doc</a>;<BR>GTCG p.583</td>
<td ALIGN="CENTER"><a href="https://www.geometrictools.com/Documentation/IntersectionBoxCone.pdf">GTWeb doc</a></td>
<td ALIGN="CENTER"><a href="https://www.geometrictools.com/Documentation/IntersectionBoxCone.pdf">GTweb doc</a></td>
<td ALIGN="CENTER"> </td>
<td ALIGN="CENTER"> </td>
<td ALIGN="LEFT"><B>(capped) cone</B></td>
</tr>
<tr>
<td ALIGN="LEFT"><B>triangle (polygon)</B></td>
<td ALIGN="CENTER"><a href="https://www.tandfonline.com/doi/abs/10.1080/10867651.1997.10487468">Möller-Trumbore jgt 2(1)</a>: <a href="https://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/">code</a> (<a href="https://github.com/erich666/jgt-code/tree/master/Volume_02/Number_1/Moller1997a">mirror</a>), <a href="http://www.graphics.cornell.edu/pubs/1997/MT97.html">paper draft</a>;<BR><a href="http://www.siggraph.org/education/materials/HyperGraph/raytrace/raypolygon_intersection.htm">IRT p.53</a>,102;<BR><a href="#IV24">Gems IV p.24</a>;<BR><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9172&rep=rep1&type=pdf">Held jgt 2(4)</a>;<BR><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR>3DG p.17;<BR><a href="https://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/">Möller</a> (<a href="https://github.com/erich666/jgt-code/tree/master/Volume_02/Number_1/Moller1997a">mirror</a>);<BR>GTCG p.485;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.153,184;<BR><a href="https://www.tandfonline.com/doi/abs/10.1080/2151237X.2005.10129195">Löfstedt jgt 10(2)</a>: <a href="https://github.com/erich666/jgt-code/tree/master/Volume_10/Number_2/Lofstedt2005">code</a>, <a href="https://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/pubs/ray_tri_survey.pdf">paper draft</a><BR><a href="https://www.tandfonline.com/doi/abs/10.1080/2151237X.2005.10129201">Chirkov jgt 10(3)</a>: <a href="https://github.com/erich666/jgt-code/tree/master/Volume_10/Number_3/Chirkov2005">code</a>;<BR><a href="https://www.tandfonline.com/doi/abs/10.1080/2151237X.2005.10129208">Lagae jgt 10(4)</a>: <a href="https://github.com/erich666/jgt-code/tree/master/Volume_10/Number_4/Lagae2005">code</a>, <a href="https://web.archive.org/web/20120905133158/http://people.cs.kuleuven.be/~ares.lagae/publications/LD05ERQIT/LD05ERQIT.pdf">paper draft</a>;<BR><a href="https://web.archive.org/web/20110716101940/http://www.softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm">SoftSurfer</a>: <a href="http://geomalgorithms.com/code.html">code</a>;<BR><a href="https://www.computer.org/csdl/journal/tg/2010/03/ttg2010030434/13rRUyp7tWT ">Havel TVCG June 2009</a>;<BR><a href="http://jcgt.org/published/0002/01/05/">Woop JCGT 2(1)</a>;<BR><a href="http://jcgt.org/published/0005/03/03/">Baldwin JCGT 5(3)</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR><a href="http://graphicscodex.com/Sample2-RayTriangleIntersection.pdf">Graphics Codex</a>;<BR>RTR4 p.962;<BR><a href="http://www.iquilezles.org/www/articles/intersectors/intersectors.htm">Shadertoy</a> <a href="https://www.shadertoy.com/view/MlGcDz">(demo)</a></td>
<td ALIGN="CENTER">Check if all<BR>vertices are<BR>on one side;(<a href="https://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/tritri_tam.pdf">Möller jgt 2(2)</a>);<BR>GTCG p.534;<BR><a href="https://web.archive.org/web/20110716101940/http://www.softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm">SoftSurfer</a>: <a href="http://geomalgorithms.com/code.html">code</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a></td>
<td ALIGN="CENTER"><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9172&rep=rep1&type=pdf">Held jgt 2(4)</a>;<BR><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://www.tandfonline.com/doi/abs/10.1080/10867651.1999.10487499">Karabassi jgt 4(1)</a>;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.135,167,226;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a></td>
<td ALIGN="CENTER"><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9172&rep=rep1&type=pdf">Held jgt 2(4)</a>;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR><a href="https://www.geometrictools.com/Documentation/IntersectionTriangleCylinder.pdf">GTweb doc</a></td>
<td ALIGN="CENTER"><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9172&rep=rep1&type=pdf">Held jgt 2(4)</a>;<BR><a href="https://www.geometrictools.com/Documentation/IntersectionTriangleCone.pdf">GTweb doc</a>;<BR>GTCG p.583</td>
<td ALIGN="CENTER"><a href="https://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/tritri_tam.pdf">Möller jgt 2(2)</a>;<BR><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9172&rep=rep1&type=pdf">Held jgt 2(4)</a>;<BR><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/">Möller</a> (<a href="https://github.com/erich666/jgt-code/tree/master/Volume_02/Number_2/Moller1997b">mirror</a>);<BR>GPG p.393;<BR>GTCG p.539;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.155,172;<BR><a href="https://www.tandfonline.com/doi/abs/10.1080/10867651.2003.10487579">Shen jgt 8(1)</a>;<BR><a href="https://www.tandfonline.com/doi/abs/10.1080/10867651.2003.10487580">Guigue jgt 8(1)</a>: <a href="https://github.com/erich666/jgt-code/tree/master/Volume_08/Number_1/Guigue2003">code</a>;<BR><a href="https://web.archive.org/web/20110716101940/http://www.softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm">SoftSurfer</a>: <a href="http://geomalgorithms.com/code.html">code</a>;<BR><a href="https://www.geometrictools.com/Documentation/DynamicCollisionDetection.pdf">GTweb doc</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR>RTR4 p.972</td>
<td ALIGN="CENTER"><a href="#III236">Gems III p.236</a>;<BR><a href="#V375">Gems V p.375</a>;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.169;<BR><a href="https://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/">Möller</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR>RTR4 p.974</td>
<td ALIGN="CENTER"><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://www.geometrictools.com/Documentation/DynamicCollisionDetection.pdf">GTweb doc</a><BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a></td>
<td ALIGN="CENTER">homogeneous clipping:<BR><a href="#I84">Gems p.84</a></td>
<td ALIGN="CENTER">generalized clipping</td>
<td ALIGN="LEFT"><B>triangle (polygon)</B></td>
</tr>
<tr>
<td ALIGN="LEFT"><B>axis-aligned bounding box</B></td>
<td ALIGN="CENTER"><a href="http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter3.htm">IRT p.65</a>,104;<BR><a href="#I395">Gems p.395</a>;<BR><a href="https://dl.acm.org/doi/abs/10.1145/1198555.1198745">Smits</a>;<BR>3DG p.20;<BR><a href="http://www.codercorner.com/RayAABB.cpp">Terdiman (optimized Woo)</a>;<BR>Schroeder;<BR>GTCG p.626;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.179;<BR><a href="https://github.com/erich666/jgt-code/tree/master/Volume_09/Number_1/Mahovsky2004">Mahovsky jgt 9(1)</a>;<BR><a href="https://github.com/erich666/jgt-code/tree/master/Volume_10/Number_1/Williams2005">Williams jgt 10(1)</a> (<a href="https://dl.acm.org/doi/abs/10.1145/1198555.1198748">code</a>);<BR><a href="https://www.cg.cs.tu-bs.de/people/eisemann">Eisemann jgt 12(4)</a> (<a href="https://web.archive.org/web/20150910070400/https://www.cg.cs.tu-bs.de/media/publications/fast-rayaxis-aligned-bounding-box-overlap-tests-using-ray-slopes.pdf">code</a>);<BR><a href="http://psgraphics.blogspot.com/2016/02/new-simple-ray-box-test-from-andrew.html">Shirley 2016</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR><a href="https://github.com/constantinides/RAABB">Chatzianastasiou</a>;<BR><a href="http://jcgt.org/published/0007/03/04/">Majercik JCGT 7(3)</a>;<BR>RTR4 p.959;<BR><a href="https://medium.com/@bromanz/another-view-on-the-classic-ray-aabb-intersection-algorithm-for-bvh-traversal-41125138b525">Wiche</a>;<BR><a href="http://www.iquilezles.org/www/articles/intersectors/intersectors.htm">Shadertoy</a> <a href="https://www.shadertoy.com/view/ld23DV">(demo)</a></td>
<td ALIGN="CENTER"><a href="#IV74">Gems IV p.74</a>;<BR>GTCG p.634;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.161,222;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR>RTR4 p.970</td>
<td ALIGN="CENTER"><a href="#I335">Gems p.335</a>;<BR><a href="https://web.archive.org/web/19991129023147/http://www.gamasutra.com/features/19991018/Gomez_4.htm">Gomez</a>;<BR>GTCG p.644;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.130,165,228;<BR>Ellipsoid: <a href="https://www.geometrictools.com/Documentation/IntersectionBoxEllipsoid.pdf">GTweb doc</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR>RTR4 p.977</td>
<td ALIGN="CENTER"></td>
<td ALIGN="CENTER"><a href="https://www.geometrictools.com/Documentation/IntersectionBoxCone.pdf">GTWeb doc</a></td>
<td ALIGN="CENTER"><a href="#III236">Gems III p.236</a>;<BR><a href="#V375">Gems V p.375</a>;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.169;<BR><a href="https://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/">Möller</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR>RTR4 p.974</td>
<td ALIGN="CENTER">A.LO<=B.HI &&<BR>A.HI>=B.LO;<BR><a href="https://web.archive.org/web/19991129002900/http://www.gamasutra.com/features/19991018/Gomez_3.htm">Gomez</a>;<BR>3DG p.445;<BR>GTCG p.637;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.79,230;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR>RTR4 p.978</td>
<td ALIGN="CENTER">(<a href="#V375">Gems V p.378</a>;<BR><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://web.archive.org/web/19991129035017/http://www.gamasutra.com/features/19991018/Gomez_5.htm">Gomez</a>;<BR>GTCG p.639);<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a></td>
<td ALIGN="CENTER">(<a href="#IV83">Gems IV p.83</a>);<BR>(<a href="#V375">Gems V p.378</a>);<BR>(<a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>);<BR><a href="http://www.cse.chalmers.se/~uffe/">Assarsson</a>;<BR>3DG p. 302;(<BR>GTCG p.624);<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR>RTR4 p.986</td>
<td ALIGN="CENTER"><a href="#IV74">Gems IV p.74</a>;<BR><a href="#V375">Gems V p.378</a></td>
<td ALIGN="LEFT"><B>axis-aligned bounding box</B></td>
</tr>
<tr>
<td ALIGN="LEFT"><B>oriented bounding box</B></td>
<td ALIGN="CENTER">(IRT p.104;<BR><a href="#II247">Gems II p.247</a>);<BR><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://web.archive.org/web/19991129050752/http://www.gamasutra.com/features/19991018/Gomez_6.htm">Gomez</a>;<BR>GTCG p.630;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.179;<BR><a href="http://www.iquilezles.org/www/articles/intersectors/intersectors.htm">Shadertoy</a> <a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR>RTR4 p.960;<BR><a href="https://www.shadertoy.com/view/ld23DV">(demo)</a></td>
<td ALIGN="CENTER"><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://web.archive.org/web/19991127082151/http://www.gamasutra.com/features/19991018/Gomez_7.htm">Gomez</a>;<BR>GTCG p.635;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.161;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR>RTR4 p.972</td>
<td ALIGN="CENTER"><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.132,166<BR><a href="https://www.semanticscholar.org/paper/An-Efficient-Ellipsoid-OBB-Intersection-Test-Larsson/0af6971bb3fc403cdd27e32d81d78497fc57b574?p2df">Larsson</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a></td>
<td ALIGN="CENTER"></td>
<td ALIGN="CENTER"><a href="https://www.geometrictools.com/Documentation/IntersectionBoxCone.pdf">GTweb doc</a></td>
<td ALIGN="CENTER"><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://www.geometrictools.com/Documentation/DynamicCollisionDetection.pdf">GTweb doc</a><BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a></td>
<td ALIGN="CENTER">(<a href="#V375">Gems V p.378</a>;<BR><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://web.archive.org/web/19991129035017/http://www.gamasutra.com/features/19991018/Gomez_5.htm">Gomez</a>;<BR>GTCG p.639);<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a></td>
<td ALIGN="CENTER"><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://web.archive.org/web/19991129035017/http://www.gamasutra.com/features/19991018/Gomez_5.htm">Gomez</a>;<BR>3DG p.449;<BR>GTCG p.639;<BR><a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a>;<BR>RTCD p.101;<BR><a href="https://www.geometrictools.com/Documentation/DynamicCollisionDetection.pdf">GTweb doc</a>;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR>RTR4 p.980</td>
<td ALIGN="CENTER"><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://www.geometrictools.com/Documentation/IntersectionBox3Frustum3.pdf">GTweb doc</a>;<BR><a href="http://www.cse.chalmers.se/~uffe/">Assarsson</a>;<BR>GTCG p.624;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a></td>
<td ALIGN="CENTER">(<a href="#IV83">Gems IV p.83</a>)</td>
<td ALIGN="LEFT"><B>oriented bounding box</B></td>
</tr>
<tr>
<td ALIGN="LEFT"><B>viewing frustum</B></td>
<td ALIGN="CENTER">(IRT p.104;<BR><a href="#II247">Gems II p.247</a>)</td>
<td ALIGN="CENTER"> </td>
<td ALIGN="CENTER"><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="http://www.cse.chalmers.se/~uffe/">Assarsson</a>;<BR>GPG p.433;<BR>3DG p.302;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR>RTR4 p.984</td>
<td ALIGN="CENTER">GPG p.380</td>
<td ALIGN="CENTER"> </td>
<td ALIGN="CENTER">homogeneous clipping:<BR><a href="#I84">Gems p.84</a></td>
<td ALIGN="CENTER">(<a href="#IV83">Gems IV p.83</a>);<BR>(<a href="#V375">Gems V p.378</a>);<BR>(<a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>);<BR><a href="http://www.cse.chalmers.se/~uffe/">Assarsson</a>;<BR>3DG p. 302;(<BR>GTCG p.624);<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a>;<BR>RTR4 p.986</td>
<td ALIGN="CENTER"><a href="https://www.geometrictools.com/Samples/Geometrics.html">GTweb</a>;<BR><a href="https://www.geometrictools.com/Documentation/IntersectionBox3Frustum3.pdf">GTweb doc</a>;<BR><a href="http://www.cse.chalmers.se/~uffe/">Assarsson</a>;<BR>GTCG p.624;<BR><a href="https://github.com/gszauer/GamePhysicsCookbook">GPC</a></td>
<td ALIGN="CENTER">(<a href="#IV83">Gems IV p.83</a>)</td>
<td ALIGN="CENTER">(<a href="#IV83">Gems IV p.83</a>)</td>
<td ALIGN="LEFT"><B>viewing frustum</B></td>
</tr>
<tr>
<td ALIGN="LEFT"><B>convex polyhedron</B></td>
<td ALIGN="CENTER">IRT p.104;<BR><a href="#II247">Gems II p.247</a>;<BR>GTCG p.493;<BR><a href="https://github.com/erich666/jgt-code/tree/master/Volume_08/Number_4/Platis2003">Platis jgt 8(4)</a>;<BR>RTCD p.198;<BR><a href="https://web.archive.org/web/20110725233122/http://www.softsurfer.com/Archive/algorithm_0111/algorithm_0111.htm">SoftSurfer</a>: <a href="http://geomalgorithms.com/code.html">code</a></td>
<td ALIGN="CENTER"> </td>
<td ALIGN="CENTER">3DG p.462;<BR>RTCD p.142</td>
<td ALIGN="CENTER"> </td>
<td ALIGN="CENTER"> </td>
<td ALIGN="CENTER">generalized clipping</td>
<td ALIGN="CENTER"><a href="#IV74">Gems IV p.74</a>;<BR><a href="#V375">Gems V p.378</a></td>
<td ALIGN="CENTER">(<a href="#IV83">Gems IV p.83</a>)</td>
<td ALIGN="CENTER">(<a href="#IV83">Gems IV p.83</a>)</td>
<td ALIGN="CENTER"><a href="#IV83">Gems IV p.83</a>;<BR>3DG p.453;(<BR><a href="https://www.geometrictools.com/Documentation/MethodOfSeparatingAxes.pdf">GTweb doc</a>;<BR>GTCG p.726;<BR><a href="http://vcg.isti.cnr.it/Publications/2003/GPR03/fast_tetrahedron_tetrahedron_overlap_algorithm.pdf">Ganovelli jgt 7(2)</a>;<BR>RTCD p.383,399,410;<BR><a href="http://twvideo01.ubm-us.net/o1/vault/gdc2013/slides/822403Gregorius_Dirk_TheSeparatingAxisTest.pdf">Gregorius 2013</a></td>
<td ALIGN="LEFT"><B>convex polyhedron</B></td>
</tr>
<tr>
<td> </td>
<td ALIGN="CENTER"><B>ray</B></td>
<td ALIGN="CENTER"><B>plane</B></td>
<td ALIGN="CENTER"><B>sphere</B></td>
<td ALIGN="CENTER"><B>cylinder</B></td>
<td ALIGN="CENTER"><B>cone</B></td>
<td ALIGN="CENTER"><B>triangle</B></td>
<td ALIGN="CENTER"><B>AABB</B></td>
<td ALIGN="CENTER"><B>OBB</B></td>
<td ALIGN="CENTER"><B>frustum</B></td>
<td ALIGN="CENTER"><B>polyhedron</B></td>
<td> </td>
</tr>
</table>
</div>
<P>
References are listed in historical order, so it's usually best to look
at the last reference first. References in parentheses indicate algorithms that will work, but are not optimized
for the particular primitives. Note that all AABB algorithms can also be used
for OBB intersections (simply transform the other primitive to the OBB's
space), so we do not list these in the table.
<H2>Dynamic Object Intersections</H2>
These are intersections in which the objects are moving relative to one another. Linear motion (only) is assumed; there is research on rotational motion collision detection, not covered here. The <a href="https://github.com/teikitu-rti/teikitu_release/tree/master/teikitu_sdk/TgS%20COLLISION">TgS</a> collision system (non-commercial use only) has many methods in this area, and the book <I>Real-Time Collision Detection</I> covers the subject in some depth.
Other relevant presentations can be found on the <a href="https://www.essentialmath.com/tutorial.htm">Essential Math for Games Programmers</a> site.
One principle is that even if both objects are moving, only one has to be considered moving. That is, one object's movement vector can be subtracted from both objects, leaving one object at rest. Another principle is to perform a <a href="https://algorist.com/problems/Minkowski_Sum.html">Minkowski sum</a> (or <a href="http://twvideo01.ubm-us.net/o1/vault/gdc2013/slides/822403Gregorius_Dirk_TheSeparatingAxisTest.pdf">Minkowski difference</a>) of the moving sphere with the other object, essentially shrinking the moving sphere to a ray. A set of static intersection tests are used in many of these tests, so look in the table above for these. The tests below are categorized as <I>boolean</I>, i.e., whether the objects intersect at all, or <I>location</I>, where the actual intersection location where the two moving objects first hit is formed. <I>(Please let me know if you have simple ways of making a given boolean test into a location test.)</I>
<P>
<B>Ray/Moving Sphere:</B> <I>(location)</I> Form a cylinder between the two spheres, intersect the two spheres and cylinder with the ray. See <a href="http://media.steampowered.com/apps/valve/2015/DirkGregorius_Contacts.pdf">Gregorius 2015</a>.<br>
<B>Ray/Moving Triangle:</B> <I>(boolean)</I> If each triangle is entirely on one side of the plane formed by the other triangle, form the polyhedron between the two triangles. The connecting faces are formed by all the combinations of an edge on one triangle and a vertex on the other. Discard any separating planes formed (i.e., use only planes in which both triangles are on the same side of the plane). Shoot the ray against it using <a href="http://www.realtimerendering.com/intersections.html#II247">ray/polyhedron testing</a>. <I>(Short of splitting the triangles into two parts each and forming volumes amongst these, is there an elegant way to perform this operation when one triangle's plane splits the other triangle?)</I><br>
<B>Ray/Moving AABB:</B> <I>(boolean)</I> Form a <a href="http://www.realtimerendering.com/downloads/shaft.zip">shaft</a> (<a href="http://www.erichaines.com/ShaftCulling.pdf">paper</a>) between the beginning and ending position of the AABB and shoot the ray against it using <a href="http://www.realtimerendering.com/intersections.html#II247">ray/polyhedron testing</a>. See <a href="http://www.realtimerendering.com/Real-Time_Rendering_4th-Collision_Detection.pdf">RTR4, free Collision Detection chapter</a>.<br>
<B>Ray/Moving OBB:</B> <I>(boolean)</I> An inelegant way is to form all combinations of edge/vertex pairs and form planes to bound the OBBs (see Ray/Moving triangle, above).</br>
<B>Ray/Moving Polyhedron:</B> Take the convex hull of each polyhedron and then the convex hull of both of these. <a href="http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=504">Glassner</a> is the earliest reference I know. See <a href="http://media.steampowered.com/apps/valve/2015/DirkGregorius_Contacts.pdf">Gregorius 2015</a> for a modern treatment.
<P>
<B>Plane/Moving Sphere:</B> <I>(location)</I> Transform the problem into changing the plane into a thick slab, of thickness equal to the radius of the sphere. Change the sphere's path into a line segment. Perform slab/line segment intersection, i.e., ray/plane intersection for the two sides of the slab. See <a href="https://web.archive.org/web/19991128214140/http://www.gamasutra.com/features/19991018/Gomez_1.htm">Gomez</a>; and <a href="http://www.realtimerendering.com/Real-Time_Rendering_4th-Collision_Detection.pdf">RTR4, free Collision Detection chapter</a>..<br>
<B>Plane/Moving AABB:</B> <I>(location)</I> If the plane's normal is along one of the primary axes, e.g., it is [0 1 0], [0 0 -1], etc., then turn the problem into slab/line segment intersection, similar to plane/moving sphere above. That is, take the thickness of the AABB and make the plane this thick.<br>
<P>
The general principal of intersecting a moving sphere against an object is to simplify thinking about the problem by making the sphere into a line segment between its center's start and end locations, while "adding" this sphere (a <a href="https://algorist.com/problems/Minkowski_Sum.html">Minkowski sum</a>) to the other object.<br>
<B>Moving Sphere/Sphere:</B> <I>(location)</I> Add the radius of the moving sphere to the static sphere, and treat the moving sphere as a ray. Use this ray to perform ray/sphere intersection. See <a href="https://web.archive.org/web/19991128214140/http://www.gamasutra.com/features/19991018/Gomez_1.htm">Gomez</a> and <a href="http://www.realtimerendering.com/Real-Time_Rendering_4th-Collision_Detection.pdf">RTR4, free Collision Detection chapter</a>..<br>
<B>Moving Sphere/Triangle:</B> <I>(location)</I> Similar to above, turn the sphere into a ray. The triangle turns into a solid defined by a set of spheres at the vertices, cylinders along the edges, and a slab for the interior of the triangle. See <a href="https://github.com/jrouwe/SweptEllipsoid">Rouwé's article and code</a>; <a href="https://www.geometrictools.com/Documentation/IntersectionMovingSphereTriangle.pdf">GTWeb doc</a>; <a href="http://www.realtimerendering.com/Real-Time_Rendering_4th-Collision_Detection.pdf">RTR4, free Collision Detection chapter</a>.; <a href="http://twvideo01.ubm-us.net/o1/vault/gdc2013/slides/822403Gregorius_Dirk_TheSeparatingAxisTest.pdf">Gregorius 2012</a>.<br>
<B>Moving Sphere/AABB:</B> GTWeb has <a href="https://www.geometrictools.com/Documentation/IntersectionMovingSphereBox.pdf">a more detailed document on this topic. <I>(boolean)</I> A conservative test (i.e., no false misses, but can give false hits when there actually is no overlap) is to make the AABB move, so forming a <a href="http://www.realtimerendering.com/downloads/shaft.zip">shaft</a> (<a href="http://www.erichaines.com/ShaftCulling.pdf">paper</a>) between the beginning and ending position of the AABB. Test the static sphere with shaft testing. </a><br>
<P>
<B>Moving Triangle/Triangle:</B> See <a href="https://www.geometrictools.com/Documentation/MethodOfSeparatingAxes.pdf">GTweb doc</a> and <a href="https://code.google.com/archive/p/box2d/downloads">Catto 2013</a>.
<P>
<B>Moving AABB/AABB:</B> <I>(location)</I> See <a href="https://web.archive.org/web/19991129002900/http://www.gamasutra.com/features/19991018/Gomez_3.htm">Gomez</a> for a use of the Separating Axis Theorem to solve this problem. <I>(boolean)</I> Form a <a href="http://www.realtimerendering.com/downloads/shaft.zip">shaft</a> (<a href="http://www.erichaines.com/ShaftCulling.pdf">paper</a>) between the beginning and ending position of the AABB and compare the static AABB against it with shaft testing.<br>
<P>
<B>Moving OBB/OBB:</B> <I>(location)</I> See <a href="https://www.geometrictools.com/Documentation/IntersectionRotatingBoxes.pdf">GTweb doc</a>.<br>
<P>
<B>Moving Convex Polyhedra/Convex Polyhedra:</B> <I>(boolean)</I> The GTCG book, p. 615 on, gives pseudocode for using the method of separating axes to solve this problem. See <a href="https://www.geometrictools.com/Documentation/MethodOfSeparatingAxes.pdf">GTweb doc</a>.<br>
<P>
<a href="http://media.steampowered.com/apps/valve/2015/DirkGregorius_Contacts.pdf">Gregorius 2015</a> covers computing contact points among spheres, capsules, convex hulls, and meshes.
<P>
Many of the non-curved objects which are moving can be treated as forming <a href="http://www.erichaines.com/ShaftCulling.pdf">shafts</a> between the starting and ending locations, and then the shaft can be tested against a ray simply enough, or against another non-curved object by using the polyhedron/polyhedron test in <a href="#IV83">Gems IV p.83</a>. Another approach is to use the <a href="https://www.geometrictools.com/Documentation/MethodOfSeparatingAxes.pdf">Separating Axis Theorem</a> (also see <a href="https://web.archive.org/web/20000510080633/http://www.gamasutra.com/features/20000330/bobic_01.htm">Bobic</a>) to tell if the two objects overlap. However, all of these approaches are just <I>boolean</I> tests.
<P>
<H2>Article references</H2>
<B>Bobic</B> - Bobic, Nick, <a href="https://web.archive.org/web/20000510080633/http://www.gamasutra.com/features/20000330/bobic_01.htm">"Advanced Collision Detection Techniques,"</a> <I>Gamasutra</I>, March 2000.</a>
<BR>
<B>Gomez</B> - Gomez, Miguel, <a href="https://web.archive.org/web/19991128214140/http://www.gamasutra.com/features/19991018/Gomez_1.htm">"Simple Intersection Tests for Games,"</a> <I>Gamasutra</I>, October 1999.</a>
<BR>
<B>Schroeder</B> - Schroeder, Tim, "Collision Detection Using Ray Casting," <I>Game Developer Magazine</I>, pp. 50-57, August 2001.
<P>
<H2>Graphics Gems references</H2>
<B>Ray/ray:</B> <a name="I304">Ronald Goldman</a>, <I>Intersection of Two Lines in Three-Space</I>, Graphics Gems, p. 304.<br>
<B>Ray/sphere:</B> <a name="I388">Jeff Hultquist</a>, <I>Intersection of a Ray with a Sphere</I>, Graphics Gems, pp. 388-389.<br>
<B>Ray/cylinder:</B> <a name="IV356">Joseph M. Cychosz</a> and Warren N. Waggenspack, Jr., <I>Intersecting a Ray with a Cylinder</I>, Graphics Gems IV, pp. 356-365, <a href="https://github.com/erich666/GraphicsGems/blob/master/gemsiv/ray_cyl.c">includes code</a>.<br>
<B>Ray/polygon:</B> <a name="IV24">Eric Haines</a>, <a href="http://www.erichaines.com/ptinpoly"><I>Point in Polygon Strategies</I></a>, Graphics Gems IV, pp. 24-46, <a href="https://github.com/erich666/GraphicsGems/tree/master/gemsiv/ptpoly_haines">includes code</a>.<br>
<B>Ray/cone:</B> <a name="V227">Ching-Kuang Shene</a>, <I>Computing the Intersection of a Line and a Cone</I>, Graphics Gems V, pp. 227-231.<br>
<B>Ray/AABB:</B> <a name="I395">Andrew Woo</a>, <I>Fast Ray-Box Intersection</I>, Graphics Gems, pp. 395-396, <a href="https://github.com/erich666/GraphicsGems/blob/master/gems/RayBox.c">includes code</a>.<br>
<B>Ray/polyhedron:</B> <a name="II247">Eric Haines</a>, <I>Fast Ray-Convex Polyhedron Intersection</I>, Graphics Gems II, pp. 247-250, <a href="https://github.com/erich666/GraphicsGems/blob/master/gemsii/RayCPhdron.c">includes code</a>.<br>
<P>
<B>Plane/AABB and AABB/polyhedron:</B> <a name="IV74">Ned Greene</a>, <I>Detecting Intersection of a Rectangular Solid and a Convex Polyhedron</I>, Graphics Gems IV, pp. 74-82.<br>
<P>
<B>Sphere/AABB:</B> <a name="I335">Jim Arvo</a>, <I>A Simple Method for Box-Sphere Intersection Testing</I>, Graphics Gems, pp. 247-250, <a href="https://github.com/erich666/GraphicsGems/blob/master/gems/BoxSphere.c">includes code</a>.<br>
<P>
<B>Triangle/AABB:</B> <a name="III236">Doug Voorhies</a>, <I>Triangle-Cube Intersection</I>, Graphics Gems III, pp. 236-239, <a href="https://github.com/erich666/GraphicsGems/blob/master/gemsiii/triangleCube.c">includes code</a>.<br>
<B>Triangle/AABB and AABB/polyhedron:</B> <a name="V375">Green and Hatch</a>, <I>Fast Polygon-Cube Intersection Testing</I>, Graphics Gems V, pp. 375-379, <a href="https://github.com/erich666/GraphicsGems/tree/master/gemsv/ch7-2/">includes code</a>.<br>
<B>Triangle/frustum:</B> <a name="I84">Paul Heckbert</a>, <I>Generic Convex Polygon Scan Conversion and Clipping</I>, Graphics Gems, pp. 84-86, <a href="https://github.com/erich666/GraphicsGems/tree/master/gems/PolyScan/">includes code</a>.<br>
<P>
<B>Polyhedron/polyhedron:</B> <a name="IV83">Rich Rabbitz</a>, <I>Fast Collision Detection of Moving Convex Polyhedra</I>, Graphics Gems IV, pp. 83-109, <a href="https://github.com/erich666/GraphicsGems/blob/master/gemsiv/collide.c">includes code</a>.<br>
<P>
<H2>Algorithms</H2>
Scalar values are lowercase italic: <I>a, n, t</I>. Vectors are lowercase bold: <B>p, v, x</B>. Matrices are uppercase bold: <B>M, T</B>. "X" denotes a cross product, "^2" means "squared", "||<B>x</B>||" means the length of vector <B>x</B>.
<P><font size="+1">
<B>Ray/ray:</B></font> <I>(after Goldman, Graphics Gems; see his article for the derivation)</I> Define each ray by an origin <B>o</B> and a normalized (unit vector) direction <B>d</B>. The two lines are then<P>
<I>L1(t1)</I> = <B>o1</B> + <B>d1</B>*<I>t1</I><BR>
<I>L2(t2)</I> = <B>o2</B> + <B>d2</B>*<I>t2</I><BR>
<P>The solution is:<BR>
<I>t1</I> = Determinant{(<B>o2</B>-<B>o1</B>),<B>d2</B>,<B>d1</B> X <B>d2</B>} / ||<B>d1</B> X <B>d2</B>||^2<P>
and<P>
<I>t2</I> = Determinant{(<B>o2</B>-<B>o1</B>),<B>d1</B>,<B>d1</B> X <B>d2</B>} / ||<B>d1</B> X <B>d2</B>||^2<P>
If the lines are parallel, the denominator ||<B>d1</B> X <B>d2</B>||^2 is 0.<P>
If the lines do not intersect, <I>t1</I> and <I>t2</I> mark the points of closest approach on each line.
</td>
</tr>
<tr>
<td valign="top"><img src="spacer.gif" alt="" height="1" border="0"></td>
<br /></td>
</tr>
</table>
<!-- <P>
<iframe width="640" height="360" frameborder="0" src="https://www.shadertoy.com/embed/4dSGW1?gui=true&t=10&paused=true&muted=false" allowfullscreen></iframe> -->
</div> <!-- /content -->
<div id="footer" class="clearfix">
<HR>
Contact: <a href="mailto:[email protected]">Eric</a></li>
</div> <!-- /footer -->
</div> <!-- /wrapper -->
</body>
</html>