erich666 / jgt-code Goto Github PK

Hi,

in CONSTRUCT_INTERSECTION where do the values for N1 and N2 come from? e.g.

299 alpha = DOT(v1,N2) / DOT(v2,N2); \

I am looking at a bug where the eye position is directly beneath a bounding box. So, the classifier in bboxarea.cxx uses the bottom of the bounding box to calculate the area. But the orthographic view direction is parallel to the bottom of the bounding box, so the area is calculated as 0.

I think for orthographic cameras, the view direction needs to be used for classifying the silhouette, not the eye position. I think the using the max/min based on the sign of the direction would work. Maybe something like this:

int pos = ((dir[0] > 0) ?  1 : 0)   // 1 = left
        + ((dir[0] < 0) ?  2 : 0)   // 2 = right
        + ((dir[1] > 0) ?  4 : 0)   // 4 = bottom
        + ((dir[1] < 0) ?  8 : 0)   // 8 = top
        + ((dir[2] > 0) ? 16 : 0)   // 16 = front
        + ((dir[2] < 0) ? 32 : 0);  // 32 = back

Hi,

I'm trying to use the lightning fast tri_tri_intersect.c to detect triangle-triangle intersections, but I'm getting weird false positives.

The following is a stand-alone code for one such case, two disjunct triangles, for which an intersection is detected:

#include <iostream>
#include "tri_tri_intersect.c"

int main(int, char **)
{
    double v1[3];
    v1[0] = 22.374370052043300205468767671845853328704833984375;
    v1[1] = 29.5499517077955005106559838168323040008544921875;
    v1[2] = 0.69999999225848397177429660587222315371036529541015625;
    double v2[3];
    v2[0] = 22.355455793707999845310041564516723155975341796875;
    v2[1] = 29.591972981426099664759021834470331668853759765625;
    v2[2] = 0.600000003652259028541493535158224403858184814453125;
    double v3[3];
    v3[0] = 22.374370052043300205468767671845853328704833984375;
    v3[1] = 29.5499517077955005106559838168323040008544921875;
    v3[2] = 0.600000003652259028541493535158224403858184814453125;
    double v4[3];
    v4[0] = 22.355455793707999845310041564516723155975341796875;
    v4[1] = 29.591972981426099664759021834470331668853759765625;
    v4[2] = 0.8000000120163139882834002492018043994903564453125;
    double v5[3];
    v5[0] = 22.355455793707999845310041564516723155975341796875;
    v5[1] = 29.591972981426099664759021834470331668853759765625;
    v5[2] = 0.69999999225848397177429660587222315371036529541015625;
    double v6[3];
    v6[0] = 22.374370052043300205468767671845853328704833984375;
    v6[1] = 29.5499517077955005106559838168323040008544921875;
    v6[2] = 0.8000000120163139882834002492018043994903564453125;

    double start[3];
    double end[3];
    int coPlanar;
    const auto result = tri_tri_intersection_test_3d(v1, v2, v3, v4, v5, v6, &coPlanar, start, end);

    std::cout << "tri_tri_intersection_test_3d() returned " << result << std::endl;

    return 0;
}

The output is

tri_tri_intersection_test_3d() returned 1

The returned intersection edge is one of the edges of the two triangles. Here is a visualization of the two triangles and the returned intersection:

Note that almost any truncation of the vertex coordinates will remedy this case.

I know this code is two decades old, but it's still the most referenced solution to this problem, and a lot of thought was put into it.

Maybe it's intsantly clear to someone what I'm doing wrong here?
Any input here is appreciated!

\Volume_11\Number_4\Bernadon2006\Source\lut.cpp line 74

remove second fclose(fd);

The code link for

Löfsted, Marta, and Tomas Akenine-Möller, "An Evaluation Framework for Ray-Triangle Intersection Algorithms," journal of graphics tools, 10(2):13-26, 2005.

points to the old path Volume_10/Number_2/Lofsted2005 instead of the new one Volume_10/Number_2/Lofstedt2005 (note the second t, committed in 58177bd)

The files for Volume_12/Number_4/Hasselgren2007 are copies from Volume_12/Number_4/Eisemann2007.

The correct files can be found in the supplements on tandfonline.com

How to solve the problem that the code version is not compatible with my Visual Studio version

I've run into an issue with:

Volume_08/Number_1/Guigue2003/tri_tri_intersect.c

See the Matlab code below that will create this figure:

t0 = [-2.000000000000000000000000e+02 -7.661661997582373651027865e+00 1.107006972331142975463081e+02; % A
      -2.000000000000000000000000e+02 -1.532332399516475796019677e+01 1.214013944662285808817614e+02; % B
      -2.000000000000000000000000e+02 -1.041705198583709623960658e+01 1.221265882878931563482183e+02; % C
      -2.000000000000000000000000e+02 -7.661661997582373651027865e+00 1.107006972331142975463081e+02];

t1 = [-2.000000000000000000000000e+02 -1.532332399516475796019677e+01 1.214013944662285808817614e+02; % D
      -2.000147534839701108921872e+02 -5.208525992918542790732772e+00 1.110632941439465781741092e+02; % E
      -2.000000000000000000000000e+02 -1.041705198583709623960658e+01 1.221265882878931563482183e+02; % F
      -2.000000000000000000000000e+02 -1.532332399516475796019677e+01 1.214013944662285808817614e+02];

e0 = [-2.000000000000000000000000e+02 -1.148161784440646755456328e+02 1.066954011562485078457030e+02; %G
      -2.000000000000000000000000e+02 -1.041705198583709623960658e+01 1.221265882878931563482183e+02]; % H
figure( 2 );
plot3( t0(:,1), t0(:,2), t0(:,3) )
hold on;
plot3( t1(:,1), t1(:,2), t1(:,3) )
plot3( e0(:,1), e0(:,2), e0(:,3), '-o' )
hold off;
axis equal;
axis off;

For these two triangles, points B and D are congruent and points C and F are congruent. I.e. they share an edge.

In this case, one of the intersection end points comes back as one of the endpoints of the shared edge. I would expect the other intersection end point to come back as the other endpoint of the shared edge. However, instead it is a point located far away.

Point H is at point C/F.
Point G is far away.

All intersection points should lie on/within both triangles.

http://ftp.math.utah.edu/pub/tex/bib/toc/jgraphtools.html#4(3):1999
Seth Teller and Michael Hohmeyer Determining the Lines Through Four Lines
supposedly had code included on the website, but wayback machine and google don't have anything at all. Are there any offline/cd-rom archives that may have the code?

I refer to Volume_08/Number_1/Guigue2003/tri_tri_intersect.c and the line segment of intersection computation.

A line segment intersection endpoint can be computed as a linear combination of the Vertex endpoints.
I refer to the paper here: https://cis.temple.edu/~lakaemper/courses/cis350_2004/etc/moeller_triangle.pdf

In Figure 2, point B can be calculated as a linear combination of V10 and V11 using the already computed projected distances from plane pi2.

More precisely: B = (dv11 * V10 - dv10 * V11) / (dv11 - dv10)

This seems more efficient than the current implementation in CONSTRUCT_INTERSECTION which starts from nothing but the 6 original vertex points.