[jira] [Issue Comment Deleted] (MATH-1211) PolyhedronsSet.firstIntersection(Vector3D point, Line line) sometimes reports intersections on wrong end of line

["Mike Zimmerman (JIRA)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/MATH-1211?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Mike Zimmerman updated MATH-1211:
---------------------------------
    Comment: was deleted

(was: Sure thing, Luc.  Please try this code that procedurally generates a triangulated cube and repeats my tests of the PolyhedronSet interior check and intersection routines.  I'm using commons-math-3.4.

Sometimes the rays I'm casting from the origin are found to intersect a face "behind" the ray direction; I think the fi

********************************************


package trimesh;


import java.util.HashSet;
import java.util.Set;

import org.apache.commons.math3.geometry.euclidean.threed.Euclidean3D;
import org.apache.commons.math3.geometry.euclidean.threed.Line;
import org.apache.commons.math3.geometry.euclidean.threed.Plane;
import org.apache.commons.math3.geometry.euclidean.threed.PolyhedronsSet;
import org.apache.commons.math3.geometry.euclidean.threed.SubPlane;
import org.apache.commons.math3.geometry.euclidean.threed.Vector3D;
import org.apache.commons.math3.geometry.euclidean.twod.PolygonsSet;
import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
import org.apache.commons.math3.geometry.partitioning.Region;
import org.apache.commons.math3.geometry.partitioning.SubHyperplane;

public class IntersectionTest {
	
	static PolyhedronsSet polyset;
	static double tol=1e-8;
	
	public static void createCubeFromTriangles() {
		Vector3D[] verts=new Vector3D[8];
		double xmin=-1,xmax=1;
		double ymin=-1,ymax=1;
		double zmin=-1,zmax=1;
		verts[0]=new Vector3D(xmin,ymin,zmin);
		verts[1]=new Vector3D(xmax,ymin,zmin);
		verts[2]=new Vector3D(xmax,ymax,zmin);
		verts[3]=new Vector3D(xmin,ymax,zmin);
		verts[4]=new Vector3D(xmin,ymin,zmax);
		verts[5]=new Vector3D(xmax,ymin,zmax);
		verts[6]=new Vector3D(xmax,ymax,zmax);
		verts[7]=new Vector3D(xmin,ymax,zmax);
		//
		int[][] faces=new int[12][];
		faces[0]=new int[]{3,1,0};	// bottom (-z)
		faces[1]=new int[]{1,3,2};	// bottom (-z)
		faces[2]=new int[]{5,7,4};	// top (+z)
		faces[3]=new int[]{7,5,6};	// top (+z)
		faces[4]=new int[]{2,5,1};	// right (+x)
		faces[5]=new int[]{5,2,6};	// right (+x)
		faces[6]=new int[]{4,3,0};	// left (-x)
		faces[7]=new int[]{3,4,7};	// left (-x)
		faces[8]=new int[]{4,1,5};	// front (-y)
		faces[9]=new int[]{1,4,0};	// front (-y)
		faces[10]=new int[]{3,6,2};	// back (+y)
		faces[11]=new int[]{6,3,7};	// back (+y)
		//
		Set<SubHyperplane<Euclidean3D>> pset=new HashSet<>();
		for (int f=0; f<faces.length; f++) {
			int[] vidx=faces[f];
			Plane p=new Plane(verts[vidx[0]],verts[vidx[1]],verts[vidx[2]],tol);
			checkNormal(p);
			Vector2D p0=p.toSubSpace(verts[vidx[0]]);
			Vector2D p1=p.toSubSpace(verts[vidx[1]]);
			Vector2D p2=p.toSubSpace(verts[vidx[2]]);
			PolygonsSet lset=new PolygonsSet(tol,p0,p1,p2);
			pset.add(new SubPlane(p,lset));
		}
		polyset=new PolyhedronsSet(pset,tol);
	}
	
	public static void checkNormal(Plane p) {
		if (p.getNormal().dotProduct(p.getOrigin())<0)
			System.out.println("Normal bad");
		else
			System.out.println("Normal ok");
	}
	
	public static void interiorTest() {
		int npts=10;
		for (int i=0; i<npts; i++) {
			Vector3D pos=new Vector3D(2*Math.random()-1,2*Math.random()-1,2*Math.random()-1).scalarMultiply(1.25);	// pick random point in cube of size 1.25; it could be inside or outside the cube
			if (polyset.checkPoint(pos).equals(Region.Location.OUTSIDE))	// check to see if it is inside or outside
				System.out.println("Point "+pos+": OUTSIDE");
			else
				System.out.println("Point "+pos+": INSIDE");
		}
	}
	
	public static void intersectionTest() {
		int nrays=10;
		for (int i=0; i<nrays; i++) {
			Vector3D origin=Vector3D.ZERO;
			Vector3D direction=new Vector3D(2*Math.random()-1,2*Math.random()-1,2*Math.random()-1).normalize();
			Line line=new Line(origin,origin.add(direction),tol);
			SubHyperplane<Euclidean3D> plane=polyset.firstIntersection(origin, line);
			if (plane==null)
				System.out.println("No intersection for ray from "+origin+" along "+direction);
			else {
				Vector3D intersectionPoint=((Plane)plane.getHyperplane()).intersection(line);
				System.out.println("Ray from "+origin+" along "+direction+" intersects cube at "+intersectionPoint);
				System.out.println("Direction of intersection point from origin is "+intersectionPoint.normalize()+", which should match the ray direction");
				double dotProduct=direction.dotProduct(intersectionPoint.subtract(origin));
				System.out.println("   (ray direction) dot (intersectionPoint-origin) = "+dotProduct);
				if (dotProduct<0) {
					System.out.println("    *****  the dot product should be positive *****");
					System.out.println("    *****  i.e. the intersection should lie in *front* of the ray not behind *****");
				}
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		createCubeFromTriangles();
		System.out.println();
		interiorTest();
		System.out.println();
		intersectionTest();
	}

}
)

> PolyhedronsSet.firstIntersection(Vector3D point, Line line) sometimes reports intersections on wrong end of line
> ----------------------------------------------------------------------------------------------------------------
>
>                 Key: MATH-1211
>                 URL: https://issues.apache.org/jira/browse/MATH-1211
>             Project: Commons Math
>          Issue Type: Bug
>            Reporter: Mike Zimmerman
>         Attachments: IntersectionTest.java
>
>
> I constructed a PolyhedronsSet from a list of triangular faces representing an icosphere (using the instructions found at https://mail-archives.apache.org/mod_mbox/commons-user/201208.mbox/<50...@free.fr>).  This seems to produce correct INSIDE/OUTSIDE results for randomly chosen points.  I think my mesh triangles are defined appropriately.
> However, using PolyhedronsSet.firstIntersection(Vector3D point, Line line) to shoot randomly oriented rays from the origin sometimes gives a wrong mesh intersection point "behind" the origin.  The intersection algorithm is sometimes picking up faces of the sphere-shaped mesh on the wrong semi-infinite portion of the line, i.e. meshIntersectionPoint.subtract(point).dotProduct(line.getDirection())<0 where point is the Vector3D at center of the sphere and line extends outward through the mesh.
> I think the dot product above should always be positive. If multiple intersections exist along a "whole" line then the first one in "front" of the line's origin should be returned. This makes ray tracing with a PolyhedronsSet possible.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)