

Home Astronomy research Software instruments Stellar equation of states EOS with ionization EOS for supernovae Chemical potentials Stellar atmospheres Voigt Function Jeans escape Polytropic stars Cold white dwarfs Hotter white dwarfs Cold neutron stars Stellar opacities Neutrino energy loss rates Ephemeris routines FermiDirac functions Galactic chemical evolution Coating an ellipsoid Universal twobody problem Nuclear reaction networks Nuclear statistical equilibrium Laminar deflagrations CJ detonations ZND detonations Fitting to conic sections Unusual linear algebra Derivatives on uneven grids Pentadiagonal solver Quadratics, Cubics, Quartics Supernova light curves Exact Riemann solutions 1D PPM hydrodynamics Verification problems Plane  cube Intersection Phyllotaxis The pendulum Circular and elliptical 3 body MESA MESAWeb FLASH Zingale's software Brown's dStar GR1D code Iliadis' STARLIB database Herwig's NuGRID Meyer's NetNuc Presentations Illustrations Videos Bicycle adventures AAS Journals 2017 MESA Marketplace 2017 MESA Summer School 2017 ASU+EdX AST111x Teaching materials Education and Public Outreach Contact: F.X.Timmes my one page vitae, full vitae, research statement, and teaching statement. 
The intersection between a box and a plane is a geometric computation with numerous applications in computer graphics, solid modeling, and computational physics (e.g., fraction of cell that may be partial ionized or covered by a burning front). Most of the raybox algorithms we could find provided a binary answer to the question of whether a given ray, the normal to the plane, was inside a specied box or not, while a few algorithms computed the vertices of the intersection plane. Here we give two methods (public_volume_fraction.tbz, and public_triangular_pyramid.tbz) to compute the volume of the intersection between a cube and a plane. The first method is based on computing the volume of an arbitrary polyhedron given the vertices of each bounding face, while the second method is founded on adding and subtracting triangular pyramids. Both methods give volume fractions that have a maximum relative difference of 10^{7}, but the triangular pyramid method has a smaller operational count. General Polyhedra Method The intersection between a cube and a plane results in an inscribed, irregular polygon with one of five basic shapes that have 3 to 6 intersection points, as illustrated in figure below. The resulting irregular polyhedron is composed of 4 to 7 faces, 6 to 14 edges, 4 to 9 vertices, and satisfies the Euler identity N_{faces}  N_{edges} + N_{vertices} = 2. Our approach extends the method of Salama & Kolb (2005) by simulateously constructing the faces, edges, vertices, and volume of the irregular polyhedron.
We work on the unit cube with vertices and faces enumerated and ordered as shown by the figure above. There are only three independent paths from the front vertex V_{1} to the back vertex V_{8} as marked by the black, dark gray, and light gray lines. The intersecting plane is defined by the length of the normal ray dl, and the spherical angles 0 ≤ θ ≤ 2π and 0 ≤ φ &le π. The maximum length of the normal ray in this coordinate system is dl_{max}/dx = (cos(θ) + sin(θ)) sin(φ) + cos(φ), otherwise the plane does not intersect the cube. We begin by forming the Cartesian coordinates of the normal ray and take the equation of the plane to be in Hessian normal form where n hat is the unit normal vector. Edge E_{ i → j} between vertices V_{i} and V_{j} of the cube can be described by the straight line and the intersection point between the plane and the straight line spanned by Edge E_{ i → j} is calculated as There is a valid intersection point only if 0 ≤ λ ≤ 1, otherwise the plane does not intersect the edge within the cube. The denominator becomes zero only if the edge is coplanar with the plane. In this case, we simply ignore the intersection. A key point in performing the planeedge intersection calculations is to maintain a consistent ordering, clockwise or counterclockwise, of the intersection points such that the final result forms a valid polygon. A consistent ordering can be achieved by traversing the edges in a manner described by Salama & Kolb (2005). There are only 3 independent paths from the front vertex V_{1} to the back vertex V_{8}. These independent paths, which do not share any vertices other than the start and end vertex, are constructed by requiring the edges of each path form a righthanded orientation. Figure 6 shows the three independent paths as the black, dark gray, and light gray solid lines. These three independent paths can determine 3 of the 6 intersection points. If there are more than 3 intersecting points, they must lie on one or more of the three dotted lines in the fgure above and must be inserted between the intersection points determined by the 3 independent paths. For example, consider the dark gray dotted edge E_{ 3 → 7} is calculated as If there exists a valid intersection with this edge, then it must be inserted between the intersection points determined by solid dark gray path and the solid black path. We start accumulating the intersection points with the light gray path by checking edges E_{ 1 → 2} for a valid intersection. If there is no intersection, we continue along the light gray path by checking E_{ 2 → 5} and then onto E_{ 5 → 7} if there is still no intersection. If an intersection point exists along the light gray path, we terminate the search along the light gray path and add the relevant vertices to a polyhedron face list. Next we check the dashed light gray path E_{ 2 → 6}, adding the face information for the resulting polyhedron if there is an intersection point. Similiarily we traverse the dark gray paths E_{ 1 → 3}, E_{ 3 → 6} E_{ 6 → 8}, E_{ 3 → 7} followed by black paths E_{ 1 → 4}, E_{ 4 → 7}, E_{ 7 → 8}, E_{ 4 → 5} In this manner we determine all the intersection points in a sequence that forms a valid polygon while simultaneously constructing the face and vertex information of the resulting irregular polyhedra. The movie below shows the number of vertices of the intersecting polygon in the θφ plane as a function of the length of the normal ray dl.
Finally, to calculate the total volume of the polyhedron, which equals the volume fraction on a unit cube, we sum the individual volumes of a series of pyramids, V = ∑ 1/3 · base · height. Each face of the polyhedron forms the base of one pyramid and the point V_{1} is arbitrarily chosen as the height of each pyramid. The area of each base (face) is calculated by transforming the base into a coordinate system where the faces zcoordinates are zero and then applying the Surveyors Formula. Note the choice of V_{1} as the reference height point means pyramids with faces 1, 4, and 5 as the base have zero volume because these pyramids have zero height. The movie above shows the volume fraction in the θφ plane as a function of the length of the normal ray dl. Triangular Pyramid Method Our triangular pyramid method constructs 9 explicit formula for the volume of the polyhedron generated by the intersection a plane with a cube. The intersecting plane is defined by the length of the normal ray dl, and the spherical angles 0 ≤ α ≤ 2π and π/2 ≤ β ≤ π/2. The maximum length of the normal ray in this coordinate system is dl_{max}/dx = (cos(α) + sin(α)) cos(β) + sin(β), otherwise the plane does not intersect the cube. Reflection symmetry about dl_{max}/2 allows the same 9 formula to be reused. We work on a cube whose edges have length dx. We begin by forming the distances along the coordinate axes of the intersecting plane We limit α and β values near 0 and π/2 such that the denominators do not go to zero. The simplest pyramid has x < dx, y < dx, and z < dx and volume fraction 


Please cite the relevant references if you publish a piece of work that use these codes, pieces of these codes, or modified versions of them. Offer coauthorship as appropriate. 
