inline
unsigned int point_in_triangle(Vertex point, Vertex triangle[3])
{
// from http://www.blackpawn.com/texts/pointinpoly/default.html
Vertex v0 = triangle[2] - triangle[0];
Vertex v1 = triangle[1] - triangle[0];
Vertex v2 = point - triangle[0];
double dot00 = dot(v0, v0);
double dot01 = dot(v0, v1);
double dot02 = dot(v0, v2);
double dot11 = dot(v1, v1);
double dot12 = dot(v1, v2);
double invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
double u = (dot11 * dot02 - dot01 * dot12) * invDenom;
double v = (dot00 * dot12 - dot01 * dot02) * invDenom;
if ((u > 0) && (v > 0) && (u + v < 1))
{
return 3;
}
else if ((u == 0) || (v == 0) || (u + v == 1))
{
return 1;
}
return 0;
}
inline
bool triangle_in_triangle(Vertex triangle1[3], Vertex triangle2[3])
{
unsigned int a = 0, b = 0;
for (unsigned int i = 0; i < 3; i++)
{
a += point_in_triangle(triangle1, triangle2);
if (a > 2)
{
return true;
}
b += point_in_triangle(triangle2, triangle1);
if (b > 2)
{
return true;
}
}
return false;
}
inline
bool triangle_intersects_triangle(Vertex triangle1[3], Vertex triangle2[3])
{
Vertex *a, *b, *c, *d;
double s, s_denominator;
double t, t_denominator;
//unsigned int match = 0, touch = 0;
for (unsigned int i = 0; i < 3; i++)
{
a = &triangle1;
if (i != 2)
{
b = &triangle1;
}
<span class="cpp-keyword">else</span>
{
b = &triangle1[<span class="cpp-number">0</span>];
}
<span class="cpp-keyword">for</span> (<span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> j = <span class="cpp-number">0</span>; j < <span class="cpp-number">3</span>; j++)
{
c = &triangle2[j];
<span class="cpp-keyword">if</span> (j != <span class="cpp-number">2</span>)
{
d = &triangle2[j + <span class="cpp-number">1</span>];
}
<span class="cpp-keyword">else</span>
{
d = &triangle2[<span class="cpp-number">0</span>];
}
<span class="cpp-comment">// since: a + s(b - a) = c + t(d - c) where t and s are scalars</span>
<span class="cpp-comment">// from this vector equation follow 3 normal equations (x, y and z)</span>
<span class="cpp-comment">// since we have 2 unknowns, we can scrap one equation for being dependant</span>
s_denominator = ((b->y - a->y) * (d->x - c->x) - (b->x - a->x) * (d->y - c->y));
<span class="cpp-keyword">if</span> (s_denominator)
{
s = ((c->y - a->y) * (d->x - c->x) + (a->x - c->x) * (d->y - c->y)) / s_denominator;
<span class="cpp-keyword">if</span> (s > <span class="cpp-number">0</span> && s < <span class="cpp-number">1</span>)
{
t_denominator = ((d->y - c->y) * (b->x - a->x) - (d->x - c->x) * (b->y - a->y));
<span class="cpp-keyword">if</span> (t_denominator)
{
t = ((a->y - c->y) * (b->x - a->x) + (c->x - a->x) * (b->y - a->y)) / t_denominator;
<span class="cpp-keyword">if</span> (t > <span class="cpp-number">0</span> && t < <span class="cpp-number">1</span>)
{
<span class="cpp-keyword">return</span> <span class="cpp-keyword">true</span>; <span class="cpp-comment">// edges intersect</span>
}
}
}
}
}
}
<span class="cpp-keyword">return</span> <span class="cpp-keyword">false</span>;
}
<span class="cpp-keyword">inline</span>
<span class="cpp-keyword">bool</span> triangle_overlaps_triangle(Vertex triangle1[<span class="cpp-number">3</span>], Vertex triangle2[<span class="cpp-number">3</span>])
{
<span class="cpp-keyword">if</span> (triangle_intersects_triangle(triangle1, triangle2))
{
<span class="cpp-keyword">return</span> <span class="cpp-keyword">true</span>;
}
<span class="cpp-keyword">else</span> <span class="cpp-keyword">if</span> (triangle_in_triangle(triangle1, triangle2))
{
<span class="cpp-keyword">return</span> <span class="cpp-keyword">true</span>;
}
<span class="cpp-keyword">return</span> <span class="cpp-keyword">false</span>;
}
<span class="cpp-keyword">bool</span> triangle_overlaps_convex(Vertex triangle[<span class="cpp-number">3</span>], Vertex *convex, <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> n)
{
<span class="cpp-keyword">if</span> (n > <span class="cpp-number">2</span>) <span class="cpp-comment">// has it got any surface?</span>
{
<span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> changing = <span class="cpp-number">0</span>, <span class="cpp-comment">// next changing vertex of convex triangle</span>
cw_i = <span class="cpp-number">1</span>, <span class="cpp-comment">// current vertex clockwise</span>
ccw_i = n - <span class="cpp-number">1</span>; <span class="cpp-comment">// current vertex counter clockwise</span>
Vertex convex_triangle[<span class="cpp-number">3</span>] = {convex[<span class="cpp-number">0</span>], convex[<span class="cpp-number">1</span>], convex[n - <span class="cpp-number">1</span>]};
<span class="cpp-keyword">bool</span> is_cw[<span class="cpp-number">3</span>] = {<span class="cpp-keyword">true</span>, <span class="cpp-keyword">true</span>, <span class="cpp-keyword">false</span>}; <span class="cpp-comment">// which convex triangle vertices do currently use cw or ccw value</span>
<span class="cpp-comment">// go through all neccessary triangles within the convex to cover the whole convex</span>
<span class="cpp-keyword">for</span> (<span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> i = <span class="cpp-number">0</span>; i < (n - <span class="cpp-number">2</span>); i++) <span class="cpp-comment">// n - 2 triangles</span>
{
<span class="cpp-keyword">if</span> (triangle_overlaps_triangle(triangle, convex_triangle))
{
<span class="cpp-keyword">return</span> <span class="cpp-keyword">true</span>;
}
<span class="cpp-keyword">if</span> (i < (n - <span class="cpp-number">3</span>))
{
<span class="cpp-keyword">if</span> (is_cw[changing])
{
ccw_i–;
convex_triangle[changing] = convex[ccw_i];
is_cw[changing] = <span class="cpp-keyword">false</span>;
}
<span class="cpp-keyword">else</span>
{
cw_i++;
convex_triangle[changing] = convex[cw_i];
is_cw[changing] = <span class="cpp-keyword">true</span>;
}
changing++;
<span class="cpp-keyword">if</span> (changing == <span class="cpp-number">3</span>)
{
changing = <span class="cpp-number">0</span>;
}
}
}
}
<span class="cpp-keyword">return</span> <span class="cpp-keyword">false</span>;
}
</pre></div><!–ENDSCRIPT–>
This handles about 7mil tri-tri overlap tests per second.
Thanks!
PS: performance drops significant if the convex object has multiple triangle (that is, not linear).
Gprof:
<!–STARTSCRIPT–><!–source lang="cpp"–><div class="source"><pre>Flat profile:
Each sample counts as <span class="cpp-number">0</span>.<span class="cpp-number">01</span> seconds.
% cumulative self self total
time seconds seconds calls ns/call ns/call name
<span class="cpp-number">27</span>.<span class="cpp-number">69</span> <span class="cpp-number">0</span>.<span class="cpp-number">72</span> <span class="cpp-number">0</span>.<span class="cpp-number">72</span> <span class="cpp-number">3000000</span> <span class="cpp-number">240</span>.<span class="cpp-number">00</span> <span class="cpp-number">240</span>.<span class="cpp-number">00</span> triangle_intersects_triangle(Vertex*, Vertex*)
<span class="cpp-number">25</span>.<span class="cpp-number">77</span> <span class="cpp-number">1</span>.<span class="cpp-number">39</span> <span class="cpp-number">0</span>.<span class="cpp-number">67</span> <span class="cpp-number">50000000</span> <span class="cpp-number">13</span>.<span class="cpp-number">40</span> <span class="cpp-number">13</span>.<span class="cpp-number">40</span> dot(Vertex <span class="cpp-keyword">const</span>&, Vertex <span class="cpp-keyword">const</span>&)
<span class="cpp-number">16</span>.<span class="cpp-number">92</span> <span class="cpp-number">1</span>.<span class="cpp-number">83</span> <span class="cpp-number">0</span>.<span class="cpp-number">44</span> <span class="cpp-number">30000000</span> <span class="cpp-number">14</span>.<span class="cpp-number">67</span> <span class="cpp-number">20</span>.<span class="cpp-number">67</span> Vertex::<span class="cpp-keyword">operator</span>-(Vertex <span class="cpp-keyword">const</span>&) <span class="cpp-keyword">const</span>
<span class="cpp-number">13</span>.<span class="cpp-number">08</span> <span class="cpp-number">2</span>.<span class="cpp-number">17</span> <span class="cpp-number">0</span>.<span class="cpp-number">34</span> <span class="cpp-number">10000000</span> <span class="cpp-number">34</span>.<span class="cpp-number">00</span> <span class="cpp-number">163</span>.<span class="cpp-number">00</span> point_in_triangle(Vertex, Vertex*)
<span class="cpp-number">6</span>.<span class="cpp-number">92</span> <span class="cpp-number">2</span>.<span class="cpp-number">35</span> <span class="cpp-number">0</span>.<span class="cpp-number">18</span> <span class="cpp-number">30000042</span> <span class="cpp-number">6</span>.<span class="cpp-number">00</span> <span class="cpp-number">6</span>.<span class="cpp-number">00</span> Vertex::Vertex(<span class="cpp-keyword">double</span>, <span class="cpp-keyword">double</span>, <span class="cpp-keyword">double</span>)
<span class="cpp-number">3</span>.<span class="cpp-number">85</span> <span class="cpp-number">2</span>.<span class="cpp-number">45</span> <span class="cpp-number">0</span>.<span class="cpp-number">10</span> <span class="cpp-number">3000000</span> <span class="cpp-number">33</span>.<span class="cpp-number">33</span> <span class="cpp-number">850</span>.<span class="cpp-number">00</span> triangle_overlaps_convex(Vertex*, Vertex*, <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span>)
<span class="cpp-number">3</span>.<span class="cpp-number">46</span> <span class="cpp-number">2</span>.<span class="cpp-number">54</span> <span class="cpp-number">0</span>.<span class="cpp-number">09</span> <span class="cpp-number">2000000</span> <span class="cpp-number">45</span>.<span class="cpp-number">00</span> <span class="cpp-number">860</span>.<span class="cpp-number">00</span> triangle_in_triangle(Vertex*, Vertex*)
<span class="cpp-number">1</span>.<span class="cpp-number">15</span> <span class="cpp-number">2</span>.<span class="cpp-number">57</span> <span class="cpp-number">0</span>.<span class="cpp-number">03</span> cross(Vertex <span class="cpp-keyword">const</span>&, Vertex <span class="cpp-keyword">const</span>&)
<span class="cpp-number">0</span>.<span class="cpp-number">77</span> <span class="cpp-number">2</span>.<span class="cpp-number">59</span> <span class="cpp-number">0</span>.<span class="cpp-number">02</span> main
<span class="cpp-number">0</span>.<span class="cpp-number">38</span> <span class="cpp-number">2</span>.<span class="cpp-number">60</span> <span class="cpp-number">0</span>.<span class="cpp-number">01</span> <span class="cpp-number">3000000</span> <span class="cpp-number">3</span>.<span class="cpp-number">33</span> <span class="cpp-number">816</span>.<span class="cpp-number">67</span> triangle_overlaps_triangle(Vertex*, Vertex*)
<span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">2</span>.<span class="cpp-number">60</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">2</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> GetTime()
% the percentage of the total running time of the
time program used by <span class="cpp-keyword">this</span> function.
cumulative a running sum of the number of seconds accounted
seconds <span class="cpp-keyword">for</span> by <span class="cpp-keyword">this</span> function and those listed above it.
self the number of seconds accounted <span class="cpp-keyword">for</span> by <span class="cpp-keyword">this</span>
seconds function alone. <span class="cpp-keyword">This</span> is the major sort <span class="cpp-keyword">for</span> <span class="cpp-keyword">this</span>
listing.
calls the number of times <span class="cpp-keyword">this</span> function was invoked, <span class="cpp-keyword">if</span>
<span class="cpp-keyword">this</span> function is profiled, <span class="cpp-keyword">else</span> blank.
self the average number of milliseconds spent in <span class="cpp-keyword">this</span>
ms/call function per call, <span class="cpp-keyword">if</span> <span class="cpp-keyword">this</span> function is profiled,
<span class="cpp-keyword">else</span> blank.
total the average number of milliseconds spent in <span class="cpp-keyword">this</span>
ms/call function and its descendents per call, <span class="cpp-keyword">if</span> <span class="cpp-keyword">this</span>
function is profiled, <span class="cpp-keyword">else</span> blank.
name the name of the function. <span class="cpp-keyword">This</span> is the minor sort
<span class="cpp-keyword">for</span> <span class="cpp-keyword">this</span> listing. The index shows the location of
the function in the gprof listing. <span class="cpp-keyword">If</span> the index is
in parenthesis it shows where it would appear in
the gprof listing <span class="cpp-keyword">if</span> it were to be printed.
Call graph (explanation follows)
granularity: each sample hit covers <span class="cpp-number">4</span> byte(s) <span class="cpp-keyword">for</span> <span class="cpp-number">0</span>.<span class="cpp-number">38</span>% of <span class="cpp-number">2</span>.<span class="cpp-number">60</span> seconds
index % time self children called name
<spontaneous>
[<span class="cpp-number">1</span>] <span class="cpp-number">98</span>.<span class="cpp-number">8</span> <span class="cpp-number">0</span>.<span class="cpp-number">02</span> <span class="cpp-number">2</span>.<span class="cpp-number">55</span> main [<span class="cpp-number">1</span>]
<span class="cpp-number">0</span>.<span class="cpp-number">10</span> <span class="cpp-number">2</span>.<span class="cpp-number">45</span> <span class="cpp-number">3000000</span>/<span class="cpp-number">3000000</span> triangle_overlaps_convex(Vertex*, Vertex*, <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span>) [<span class="cpp-number">2</span>]
<span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">42</span>/<span class="cpp-number">30000042</span> Vertex::Vertex(<span class="cpp-keyword">double</span>, <span class="cpp-keyword">double</span>, <span class="cpp-keyword">double</span>) [<span class="cpp-number">9</span>]
<span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">2</span>/<span class="cpp-number">2</span> GetTime() [<span class="cpp-number">14</span>]
———————————————–
<span class="cpp-number">0</span>.<span class="cpp-number">10</span> <span class="cpp-number">2</span>.<span class="cpp-number">45</span> <span class="cpp-number">3000000</span>/<span class="cpp-number">3000000</span> main [<span class="cpp-number">1</span>]
[<span class="cpp-number">2</span>] <span class="cpp-number">98</span>.<span class="cpp-number">1</span> <span class="cpp-number">0</span>.<span class="cpp-number">10</span> <span class="cpp-number">2</span>.<span class="cpp-number">45</span> <span class="cpp-number">3000000</span> triangle_overlaps_convex(Vertex*, Vertex*, <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span>) [<span class="cpp-number">2</span>]
<span class="cpp-number">0</span>.<span class="cpp-number">01</span> <span class="cpp-number">2</span>.<span class="cpp-number">44</span> <span class="cpp-number">3000000</span>/<span class="cpp-number">3000000</span> triangle_overlaps_triangle(Vertex*, Vertex*) [<span class="cpp-number">3</span>]
———————————————–
<span class="cpp-number">0</span>.<span class="cpp-number">01</span> <span class="cpp-number">2</span>.<span class="cpp-number">44</span> <span class="cpp-number">3000000</span>/<span class="cpp-number">3000000</span> triangle_overlaps_convex(Vertex*, Vertex*, <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span>) [<span class="cpp-number">2</span>]
[<span class="cpp-number">3</span>] <span class="cpp-number">94</span>.<span class="cpp-number">2</span> <span class="cpp-number">0</span>.<span class="cpp-number">01</span> <span class="cpp-number">2</span>.<span class="cpp-number">44</span> <span class="cpp-number">3000000</span> triangle_overlaps_triangle(Vertex*, Vertex*) [<span class="cpp-number">3</span>]
<span class="cpp-number">0</span>.<span class="cpp-number">09</span> <span class="cpp-number">1</span>.<span class="cpp-number">63</span> <span class="cpp-number">2000000</span>/<span class="cpp-number">2000000</span> triangle_in_triangle(Vertex*, Vertex*) [<span class="cpp-number">4</span>]
<span class="cpp-number">0</span>.<span class="cpp-number">72</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">3000000</span>/<span class="cpp-number">3000000</span> triangle_intersects_triangle(Vertex*, Vertex*) [<span class="cpp-number">6</span>]
———————————————–
<span class="cpp-number">0</span>.<span class="cpp-number">09</span> <span class="cpp-number">1</span>.<span class="cpp-number">63</span> <span class="cpp-number">2000000</span>/<span class="cpp-number">2000000</span> triangle_overlaps_triangle(Vertex*, Vertex*) [<span class="cpp-number">3</span>]
[<span class="cpp-number">4</span>] <span class="cpp-number">66</span>.<span class="cpp-number">2</span> <span class="cpp-number">0</span>.<span class="cpp-number">09</span> <span class="cpp-number">1</span>.<span class="cpp-number">63</span> <span class="cpp-number">2000000</span> triangle_in_triangle(Vertex*, Vertex*) [<span class="cpp-number">4</span>]
<span class="cpp-number">0</span>.<span class="cpp-number">34</span> <span class="cpp-number">1</span>.<span class="cpp-number">29</span> <span class="cpp-number">10000000</span>/<span class="cpp-number">10000000</span> point_in_triangle(Vertex, Vertex*) [<span class="cpp-number">5</span>]
———————————————–
<span class="cpp-number">0</span>.<span class="cpp-number">34</span> <span class="cpp-number">1</span>.<span class="cpp-number">29</span> <span class="cpp-number">10000000</span>/<span class="cpp-number">10000000</span> triangle_in_triangle(Vertex*, Vertex*) [<span class="cpp-number">4</span>]
[<span class="cpp-number">5</span>] <span class="cpp-number">62</span>.<span class="cpp-number">7</span> <span class="cpp-number">0</span>.<span class="cpp-number">34</span> <span class="cpp-number">1</span>.<span class="cpp-number">29</span> <span class="cpp-number">10000000</span> point_in_triangle(Vertex, Vertex*) [<span class="cpp-number">5</span>]
<span class="cpp-number">0</span>.<span class="cpp-number">67</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">50000000</span>/<span class="cpp-number">50000000</span> dot(Vertex <span class="cpp-keyword">const</span>&, Vertex <span class="cpp-keyword">const</span>&) [<span class="cpp-number">7</span>]
<span class="cpp-number">0</span>.<span class="cpp-number">44</span> <span class="cpp-number">0</span>.<span class="cpp-number">18</span> <span class="cpp-number">30000000</span>/<span class="cpp-number">30000000</span> Vertex::<span class="cpp-keyword">operator</span>-(Vertex <span class="cpp-keyword">const</span>&) <span class="cpp-keyword">const</span> [<span class="cpp-number">8</span>]
———————————————–
<span class="cpp-number">0</span>.<span class="cpp-number">72</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">3000000</span>/<span class="cpp-number">3000000</span> triangle_overlaps_triangle(Vertex*, Vertex*) [<span class="cpp-number">3</span>]
[<span class="cpp-number">6</span>] <span class="cpp-number">27</span>.<span class="cpp-number">7</span> <span class="cpp-number">0</span>.<span class="cpp-number">72</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">3000000</span> triangle_intersects_triangle(Vertex*, Vertex*) [<span class="cpp-number">6</span>]
———————————————–
<span class="cpp-number">0</span>.<span class="cpp-number">67</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">50000000</span>/<span class="cpp-number">50000000</span> point_in_triangle(Vertex, Vertex*) [<span class="cpp-number">5</span>]
[<span class="cpp-number">7</span>] <span class="cpp-number">25</span>.<span class="cpp-number">8</span> <span class="cpp-number">0</span>.<span class="cpp-number">67</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">50000000</span> dot(Vertex <span class="cpp-keyword">const</span>&, Vertex <span class="cpp-keyword">const</span>&) [<span class="cpp-number">7</span>]
———————————————–
<span class="cpp-number">0</span>.<span class="cpp-number">44</span> <span class="cpp-number">0</span>.<span class="cpp-number">18</span> <span class="cpp-number">30000000</span>/<span class="cpp-number">30000000</span> point_in_triangle(Vertex, Vertex*) [<span class="cpp-number">5</span>]
[<span class="cpp-number">8</span>] <span class="cpp-number">23</span>.<span class="cpp-number">8</span> <span class="cpp-number">0</span>.<span class="cpp-number">44</span> <span class="cpp-number">0</span>.<span class="cpp-number">18</span> <span class="cpp-number">30000000</span> Vertex::<span class="cpp-keyword">operator</span>-(Vertex <span class="cpp-keyword">const</span>&) <span class="cpp-keyword">const</span> [<span class="cpp-number">8</span>]
<span class="cpp-number">0</span>.<span class="cpp-number">18</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">30000000</span>/<span class="cpp-number">30000042</span> Vertex::Vertex(<span class="cpp-keyword">double</span>, <span class="cpp-keyword">double</span>, <span class="cpp-keyword">double</span>) [<span class="cpp-number">9</span>]
———————————————–
<span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">42</span>/<span class="cpp-number">30000042</span> main [<span class="cpp-number">1</span>]
<span class="cpp-number">0</span>.<span class="cpp-number">18</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">30000000</span>/<span class="cpp-number">30000042</span> Vertex::<span class="cpp-keyword">operator</span>-(Vertex <span class="cpp-keyword">const</span>&) <span class="cpp-keyword">const</span> [<span class="cpp-number">8</span>]
[<span class="cpp-number">9</span>] <span class="cpp-number">6</span>.<span class="cpp-number">9</span> <span class="cpp-number">0</span>.<span class="cpp-number">18</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">30000042</span> Vertex::Vertex(<span class="cpp-keyword">double</span>, <span class="cpp-keyword">double</span>, <span class="cpp-keyword">double</span>) [<span class="cpp-number">9</span>]
———————————————–
<spontaneous>
[<span class="cpp-number">10</span>] <span class="cpp-number">1</span>.<span class="cpp-number">2</span> <span class="cpp-number">0</span>.<span class="cpp-number">03</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> cross(Vertex <span class="cpp-keyword">const</span>&, Vertex <span class="cpp-keyword">const</span>&) [<span class="cpp-number">10</span>]
———————————————–
<span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">2</span>/<span class="cpp-number">2</span> main [<span class="cpp-number">1</span>]
[<span class="cpp-number">14</span>] <span class="cpp-number">0</span>.<span class="cpp-number">0</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">0</span>.<span class="cpp-number">00</span> <span class="cpp-number">2</span> GetTime() [<span class="cpp-number">14</span>]
———————————————–
<span class="cpp-keyword">This</span> table describes the call tree of the program, and was sorted by
the total amount of time spent in each function and its children.
Each entry in <span class="cpp-keyword">this</span> table consists of several lines. The line with the
index number at the left hand margin lists the current function.
The lines above it list the functions that called <span class="cpp-keyword">this</span> function,
and the lines below it list the functions <span class="cpp-keyword">this</span> one called.
<span class="cpp-keyword">This</span> line lists:
index A unique number given to each element of the table.
Index numbers are sorted numerically.
The index number is printed next to every function name so
it is easier to look up where the function in the table.
% time <span class="cpp-keyword">This</span> is the percentage of the `total' time that was spent
in <span class="cpp-keyword">this</span> function and its children. Note that due to
different viewpoints, functions excluded by options, etc,
these numbers will NOT add up to <span class="cpp-number">100</span>%.
self <span class="cpp-keyword">This</span> is the total amount of time spent in <span class="cpp-keyword">this</span> function.
children <span class="cpp-keyword">This</span> is the total amount of time propagated into <span class="cpp-keyword">this</span>
function by its children.
called <span class="cpp-keyword">This</span> is the number of times the function was called.
<span class="cpp-keyword">If</span> the function called itself recursively, the number
only includes non-recursive calls, and is followed by
a `+' and the number of recursive calls.
name The name of the current function. The index number is
printed after it. <span class="cpp-keyword">If</span> the function is a member of a
cycle, the cycle number is printed between the
function's name and the index number.
<span class="cpp-keyword">For</span> the function's parents, the fields have the following meanings:
self <span class="cpp-keyword">This</span> is the amount of time that was propagated directly
from the function into <span class="cpp-keyword">this</span> parent.
children <span class="cpp-keyword">This</span> is the amount of time that was propagated from
the function's children into <span class="cpp-keyword">this</span> parent.
called <span class="cpp-keyword">This</span> is the number of times <span class="cpp-keyword">this</span> parent called the
function `/' the total number of times the function
was called. Recursive calls to the function are not
included in the number after the `/'.
name <span class="cpp-keyword">This</span> is the name of the parent. The parent's index
number is printed after it. <span class="cpp-keyword">If</span> the parent is a
member of a cycle, the cycle number is printed between
the name and the index number.
<span class="cpp-keyword">If</span> the parents of the function cannot be determined, the word
`<spontaneous>' is printed in the `name' field, and all the other
fields are blank.
<span class="cpp-keyword">For</span> the function's children, the fields have the following meanings:
self <span class="cpp-keyword">This</span> is the amount of time that was propagated directly
from the child into the function.
children <span class="cpp-keyword">This</span> is the amount of time that was propagated from the
child's children to the function.
called <span class="cpp-keyword">This</span> is the number of times the function called
<span class="cpp-keyword">this</span> child `/' the total number of times the child
was called. Recursive calls by the child are not
listed in the number after the `/'.
name <span class="cpp-keyword">This</span> is the name of the child. The child's index
number is printed after it. <span class="cpp-keyword">If</span> the child is a
member of a cycle, the cycle number is printed
between the name and the index number.
<span class="cpp-keyword">If</span> there are any cycles (circles) in the call graph, there is an
entry <span class="cpp-keyword">for</span> the cycle-as-a-whole. <span class="cpp-keyword">This</span> entry shows who called the
cycle (as parents) and the members of the cycle (as children.)
The `+' recursive calls entry shows the number of function calls that
were internal to the cycle, and the calls entry <span class="cpp-keyword">for</span> each member shows,
<span class="cpp-keyword">for</span> that member, how many times it was called from other members of
the cycle.
Index by function name
[<span class="cpp-number">5</span>] point_in_triangle(Vertex, Vertex*) [<span class="cpp-number">6</span>] triangle_intersects_triangle(Vertex*, Vertex*) [<span class="cpp-number">9</span>] Vertex::Vertex(<span class="cpp-keyword">double</span>, <span class="cpp-keyword">double</span>, <span class="cpp-keyword">double</span>)
[<span class="cpp-number">4</span>] triangle_in_triangle(Vertex*, Vertex*) [<span class="cpp-number">7</span>] dot(Vertex <span class="cpp-keyword">const</span>&, Vertex <span class="cpp-keyword">const</span>&) [<span class="cpp-number">8</span>] Vertex::<span class="cpp-keyword">operator</span>-(Vertex <span class="cpp-keyword">const</span>&) <span class="cpp-keyword">const</span>
[<span class="cpp-number">2</span>] triangle_overlaps_convex(Vertex*, Vertex*, <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span>) [<span class="cpp-number">10</span>] cross(Vertex <span class="cpp-keyword">const</span>&, Vertex <span class="cpp-keyword">const</span>&) [<span class="cpp-number">1</span>] main
[<span class="cpp-number">3</span>] triangle_overlaps_triangle(Vertex*, Vertex*) [<span class="cpp-number">14</span>] GetTime()
</pre></div><!–ENDSCRIPT–> Triangle-triangle overlap test (3D, same plane)
Author
So, I have a convex shaped thingy, and a triangle, I need to test if both have overlap. So, I convert the convex to triangles (cake), then do triangle-to-triangle overlap tests. But, it's kind of slow compared to some other code...
The other code is: http://jgt.akpeters.com/papers/GuigueDevillers03/triangle_triangle_intersection.html
However, it has a very vital bug (or, unpleasant feature, w/e you want to call it) which makes that even if triangles just touch, it says they intersect. Mathematically non-sense and is not what I want. Tried to see if I could fix it, but the code is a horror to maintain (or even look at).
I'm very jealous about it's speed though, and I'd be very interested if anyone knew if this technique had a name, so I could rebuild it properly (err, maintainably). My test is like this:
I check whether triangle line-segments intersect, and I check if any of them has points in each other, or 3 points on the borders of the other (on the edge or on a vertex). It works, I'm proud, and it's quite faster then that SAT (separate axis theorem) method.
Yes, so basically, I'm looking into optimizing the current code. Does anyone know what the technique is called or where it is described of the above link?
This is the code I currently am using. Basically, I do line-line intersection tests, if they succeed, we got overlap. Then I check if either one point is inside, or 3 points are on the borders. If so, JACKPOT!
Are your triangles dynamic?
If they are static, then it's a lot faster to check point/triangle intersection by pre-calculating the edge-planes or edge-lines. Is this in 2D?
In 2D it's 'ax + by + c = 0', and you check if a point is inside with:
You might need to use '>' or '<' when comparing to 'c', depending on how you calculate your edges.
Your edge-tests also seem to use way too many calculations. You can do edge-to-edge detections also with these edge-functions, simply checking if both edges have their end-points on opposite sides of the other edge, requiring much fewer operations, and no divisions (which are usually slow).
EDIT: I missed your title.. 3D, but in the same plane should work as 2D.. =)
If they are static, then it's a lot faster to check point/triangle intersection by pre-calculating the edge-planes or edge-lines. Is this in 2D?
In 2D it's 'ax + by + c = 0', and you check if a point is inside with:
bool inside(point p, edge triangle[3]) { for(int i=0;i<3;++i) { if(dot(p, edge.ab) < edge.c) return false; } return true;}You might need to use '>' or '<' when comparing to 'c', depending on how you calculate your edges.
Your edge-tests also seem to use way too many calculations. You can do edge-to-edge detections also with these edge-functions, simply checking if both edges have their end-points on opposite sides of the other edge, requiring much fewer operations, and no divisions (which are usually slow).
EDIT: I missed your title.. 3D, but in the same plane should work as 2D.. =)
Author
Well, yes, it is a 2D problem, but it's in a 3D space, so I think I must get the plane it's in (cake) and then transform to a 2D system?
I'm a bit unsure what you mean with edge.ab and edge.c, but you did open my eyes a bit :P. I'm going to think of better 2D approaches.
PS: the triangles are fed through a map of a game, so yes, in the map it's static.
I'm a bit unsure what you mean with edge.ab and edge.c, but you did open my eyes a bit :P. I'm going to think of better 2D approaches.
PS: the triangles are fed through a map of a game, so yes, in the map it's static.
If you have a triangle in 3D, you can get the plane equation as follows:
The plane equation in that case is 'ax + by + cz - d = 0'. If you have a point and a plane, you can get the distance from the plane to that point with:
This distance is positive in front of the plane, and negative behind the plane. You can check whether a point is inside a triangle by checking the distance to the plane at each of it's edges. If the point has a positive distance to each plane, then it is inside the triangle (if the positive side is inward).
In 2D you get the edge-equation 'ax + by - c = 0' of a line with two endpoints like so:
And the 2D-distance:
Again, it's a signed distance, negative behind the line. You must remember to be consistent with the order of you points, so you always know which side is in front and behind.
If your convex shape really is convex, you don't need to convert it to triangles either, you can just test the same way, but against more edges. A point inside the convex has the same sign on the distance to all it's edges, and edge-tests can also be done the same way. Only if you have concave shapes do you need to make any more complex algorithm, for convex shapes you can just test with a loop through N points instead of 3.
vec3 triangle[3];vec3 normal = cross(triangle[0]-triangle[1], triangle[0]-triangle[2]);normal = normalize(normal);float a = normal.x;float b = normal.y;float c = normal.z;float d = dot(normal, triangle[0]);The plane equation in that case is 'ax + by + cz - d = 0'. If you have a point and a plane, you can get the distance from the plane to that point with:
vec3 point;vec3 planeNormal;float planeD;distance = dot(point, planeNormal) - planeD;This distance is positive in front of the plane, and negative behind the plane. You can check whether a point is inside a triangle by checking the distance to the plane at each of it's edges. If the point has a positive distance to each plane, then it is inside the triangle (if the positive side is inward).
In 2D you get the edge-equation 'ax + by - c = 0' of a line with two endpoints like so:
vec2 endPoints[2];vec2 normal = vec2(endPoints[1].y-endPoints[0].y, endPoints[0].x-endPoints[1].x);normal = normalize(normal);float a = normal.x;float b = normal.y;float c = dot(normal, endPoints[0]);And the 2D-distance:
vec2 point;vec2 edgeNormal;float edgeC;distance = dot(point, edgeNormal) - edgeC;Again, it's a signed distance, negative behind the line. You must remember to be consistent with the order of you points, so you always know which side is in front and behind.
If your convex shape really is convex, you don't need to convert it to triangles either, you can just test the same way, but against more edges. A point inside the convex has the same sign on the distance to all it's edges, and edge-tests can also be done the same way. Only if you have concave shapes do you need to make any more complex algorithm, for convex shapes you can just test with a loop through N points instead of 3.
Author
Thanks for your elaborate reply! :)
I heard of that technique before, and it sounds very solid, I also thought of the following:
If you traverse the points one direction round, the cross product with the the line between 2 points of the convex, and the line from one of the points to the tested point (possibly) inside the convex, then the direction of this cross product must always be the same for all points of the convex. When cross product is 0, it's on the edge.
Thanks, Erik, I think I was thinking too difficult, hehe.
I heard of that technique before, and it sounds very solid, I also thought of the following:
If you traverse the points one direction round, the cross product with the the line between 2 points of the convex, and the line from one of the points to the tested point (possibly) inside the convex, then the direction of this cross product must always be the same for all points of the convex. When cross product is 0, it's on the edge.
Thanks, Erik, I think I was thinking too difficult, hehe.
Author
It's indeed faster, as I can leave out the convex-to-triangle code. Also the point-in-triangle code is indeed faster then the one I was using.
It's not much faster for tri-tri overlap tests, but when the convex is not a tri but a quad or higher, it goes linear up in time, not exponential like I had before, so that's a great increment in efficiency.
The tri-tri line segment intersection test is still the same (be it tri-convex now, not just tri-tri). I did think of a method to merge it with the theory you gave, but the intersection test is about 2 times faster (or actually, I do the tests in a certain order, when I do the intersection test before the points-in test, its 200% as fast as if I do it vice versa.
The whole code is now a bit more then 300% slower then the 'bugged' "fastest" tri-tri intersection test, but is linear with more triangles. So I think I can be happy :D
Thanks Erik!
It's not much faster for tri-tri overlap tests, but when the convex is not a tri but a quad or higher, it goes linear up in time, not exponential like I had before, so that's a great increment in efficiency.
The tri-tri line segment intersection test is still the same (be it tri-convex now, not just tri-tri). I did think of a method to merge it with the theory you gave, but the intersection test is about 2 times faster (or actually, I do the tests in a certain order, when I do the intersection test before the points-in test, its 200% as fast as if I do it vice versa.
The whole code is now a bit more then 300% slower then the 'bugged' "fastest" tri-tri intersection test, but is linear with more triangles. So I think I can be happy :D
Thanks Erik!
Glad to help =)
If you want it even faster you should be able to use the fact that when you check point-in-triangle you do all the point-to-edge-distance checks, that are also used for edge-edge intersection testing. So avoiding recalculation, the entire thing would be 18 distance-checks, to get the distance for each of the points to the edges in the other triangle. (And early-out if a point is inside).
Also, once you know no points are inside a triangle, the only intersection case requires at least two edges of each triangle intersecting two edges in the other, so you should only need to test 4 edges, not 6, to guarantee to find an intersection if one exists. (If you do it in that order.. it probably depends on the probability of different intersections which is fastest)
If you want it even faster you should be able to use the fact that when you check point-in-triangle you do all the point-to-edge-distance checks, that are also used for edge-edge intersection testing. So avoiding recalculation, the entire thing would be 18 distance-checks, to get the distance for each of the points to the edges in the other triangle. (And early-out if a point is inside).
Also, once you know no points are inside a triangle, the only intersection case requires at least two edges of each triangle intersecting two edges in the other, so you should only need to test 4 edges, not 6, to guarantee to find an intersection if one exists. (If you do it in that order.. it probably depends on the probability of different intersections which is fastest)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
