commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Mike Zimmerman (JIRA)" <>
Subject [jira] [Issue Comment Deleted] (MATH-1211) PolyhedronsSet.firstIntersection(Vector3D point, Line line) sometimes reports intersections on wrong end of line
Date Wed, 08 Apr 2015 15:45:12 GMT


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

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);
			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");
			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");
				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 *****");

	public static void main(String[] args) {


> PolyhedronsSet.firstIntersection(Vector3D point, Line line) sometimes reports intersections
on wrong end of line
> ----------------------------------------------------------------------------------------------------------------
>                 Key: MATH-1211
>                 URL:
>             Project: Commons Math
>          Issue Type: Bug
>            Reporter: Mike Zimmerman
>         Attachments:
> I constructed a PolyhedronsSet from a list of triangular faces representing an icosphere
(using the instructions found at<>).
 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

View raw message