Le 25/08/2012 12:17, Martin Ennemoser a écrit : > Hi! Hi Martin,
> > I have a polyhedron in 3D space that consists of a triangle mesh. Now I want > to use the BSP tree to classify wheter a point is inside or outside of the > polyhedron. > The problem is that I don't know how to construct a BSP tree with my > polyhedron vertices. The user guide only gives provides little information. > Maybe someone could give me with a short code example. You can look for example at the junit tests. One example is testIssue780 in the PolyhedronsSetTest class in package org.apache.commons.math3.geometry.euclidean.threed. The algorithm used by the test is the following: 1) set up the points coordinates for all vertices of the polyhedron 2) set up the mesh triangles by using an indirection array of indices (i.e. somthing like triangle 1 uses points 1, 2 and 3, triangle 2 uses point 4, 5 and 1, traingle 3 uses ...) 3) for each triangle, create a facet using the following stages: 3a) create a 3D plane from the three points 3b) create 2D points by projecting the 3D points into the plane 3c) create three 2D lines by joining all pairs of projected 3D points 3c) create a 2D PolygonSet using the 2D lines 3d) create a 3D SubPlane using the plane and the 2D PolygonSet 4) create the PolyhedronSet using all 3D SubPlanes The main trick is the 2D/3D projection that occurs at each facet. Beware that when you create a Region from a collection of boundary elements (i.e. creating a PolygonSet from lines or creating a PolyhedronSet from facets), the elements in the boundary must be oriented, as they define which half space will be the interior and which half space will be the exterior. The convention we use is that the interior is on the minus side of the hyperplane. For lines, the plus side is the half space on the right when traveling along the line in ascending coordinate direction. This implies that if you define a square polygon, you should define the boundary in counterclockwise direction if you want the interior to be the finite square (on the left as you travel in counterclockwise direction along the boundary) and the exterior to be the infinite plane minus the central square (on the right as you travel in counterclockwise direction along the boundary). If you define the boundary in the opposite direction (i.e clockwise), the interior will be the infinite region and the exterior will be the finite square. If you define your boundary with some elements in one direction and other elements in the opposite direction, this will fail. For planes in 3D, the plus half space is towards plane normal. best regards, Luc > > Thank you! > > --------------------------------------------------------------------- > To unsubscribe, e-mail: [email protected] > For additional commands, e-mail: [email protected] > > --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
