Tirrell, Actually, I don't have a particular 3D printer that I am working with. I was interested in the general problem of identifying points that are contained inside a solid defined by a triangle mesh. I thought I could learn a little more J by attempting to develop a program to find those points. I hadn't even considered the issue of defining the print-head path for the 3D printer.
I probably should have labeled my posts "Finding the points inside a solid that fall on an intersecting plane" or some similar name, and not mentioned a 3D printer at all. However, your links to the 3D printer information were quite interesting, so I appreciate the post. I learned quite a bit about that technology from them. Skip Skip On Tue, Jun 26, 2012 at 5:23 PM, Tirrell, Jordan (Consultant) < jtirr...@thomasnet.com> wrote: > My understanding of 3D printers is that they need specific directions > for the path that the print head takes. I know Solidoodle assumes you're > starting with .stl (triangle mesh) files and recommends using Skeinforge > to create the printer head path files > (http://www.solidoodle.com/how-to-2/how-to-print/). It looks like .stl > files are pretty standard for the 3D printing community > (http://www.thingiverse.com/). I do have J code to create .stl files for > the Platonic solids. Are you working with a specific printer and > software that requires the binary 3D array format you describe? > > > -----Original Message----- > From: programming-boun...@jsoftware.com > [mailto:programming-boun...@jsoftware.com] On Behalf Of Skip Cave > Sent: Tuesday, June 26, 2012 4:03 AM > To: Programming@jsoftware.com > Subject: Re: [Jprogramming] The 3D printer problem > > For our 3D printer problem, we first look at how to create a data > structure which will define a mesh of triangles, which in turn, defines > a 3D solid. > Then we can see about defining nouns that will compute the interior > points in the solid, which would fall in each scanning plane. > > At first glance, it would seem that one could make a simple list of > triples, where a triple is a vector with three numbers that represent > the x, y, and z coordinates of a single vertex in the triangle mesh. > This data structure would be a simple 3xN array where each triple > represents one vertex in the triangle mesh. This seems quite efficient, > except for the fact that with this data structure, discovering which > verticies belong to which triangles is a non-trivial problem. The data > structure needs to somehow indicate which vertices go with which > triangles, to avoid any additional computational complexities. > > The obvious way to keep triangle data in the structure is to simply > define a 3 by 3 by N matrix. Each three-element row vector in the matrix > representing one point in 3D space and thus one vertex in the triangle > mesh. Each 3x3 array represents three vertices, which defines exactly > one triangle in the mesh, and the N 3x3 arrays then represent the N > triangles in the mesh. Since all the triangles will be sharing vertices > with other triangles, this scheme will be somewhat inefficient. This is > because the same vertex may be in several triangles, and thus repeated > in several different 3x3 matrices. However, this is probably the easiest > data structure to deal with computationally, but its inefficiency may > become problematic for large triangle meshes. > > Wikipedia presents additional proposals for triangle mesh data > structures. > The Wikipedia article "Triangle Mesh" ( > http://en.wikipedia.org/wiki/Triangle_mesh), defines two other triangle > mesh data structures, including the "Triangle Strip" and the "Index > Array" > structures, both of which reduce the vertex redundancy from the general > case I defined previously. However, with J, it is likely much easier to > deal with the fully-redundant 3x3xN matrix, as that structure should > keep extra data manipulation to a minimum. > > > This now allows us to define our first solid, the right tetrahedron I > described in my first post, using our new data structure. > > t1 =. 4 3 3 $ 0 0 0 100 0 0 0 100 0 0 0 100 > t1 > 0 0 0 > 100 0 0 > 0 100 0 > > 0 0 100 > 0 0 0 > 100 0 0 > > 0 100 0 > 0 0 100 > 0 0 0 > > 100 0 0 > 0 100 0 > 0 0 100 > > Where t1 is the data structure for our tetrahedron. Now we are ready to > try to build the point classification algorithm, which will take some > work, in order to convert Feito's algorithm to J. Any suggestions would > be appreciated.. > > Skip > > > On Tue, Jun 26, 2012 at 1:40 AM, Skip Cave <s...@caveconsulting.com> > wrote: > > > So far, no one has replied to my 3D printer problem post. Meanwhile, I > > > have been researching the problem, and I have found what looks like a > > reasonable algorithm that could be applied to the solution. The > > algorithm is described in a paper by F.R. Feito and others, entitled > > "An Efficient Point Classification Algorithm for Triangle Meshes". > > > > The paper is located at: http://elliscave.com/cc/sfrto05.pdf. > > > > The C code implementing the algorithm is at: > > http://wwwdi.ujaen.es/~gigjaen/recursos/inclusionmesh.htm > > > > This algorithm gives us a head start on the problem. We still need to > > find the points in each of the 100 scan planes that fall within the > solid. > > However, one of the first steps will be to decide how to structure the > > > data for the triangle mesh in a "J" way, which will represent the > > solid, and still lend itself to the coming computations. That will be > > my next step in this problem space. > > > > Skip > > > > > > On Mon, May 21, 2012 at 8:46 AM, Skip Cave > <s...@caveconsulting.com>wrote: > > > >> A key problem for all 3D printers is to convert a defined solid into > > >> a set of horizontal slices (planes) through the solid. Each slice > >> will represent one scan-pass of the printer head for the 3D printer > >> as it builds up the solid, one layer at a time. > >> > >> > >> Each slice through the solid should be defined as a binary 2D surface > > >> array, with a binary one in the array indicating that specific point > >> on the plane is inside the solid, and a binary zero in the array > >> indicating that the point in the plane is outside the solid. A one in > > >> the scan plane array indicates that the printer should deposit some > >> material at this point in the plane, and a zero indicates that the > >> printer should not deposit any material at this point in the plane. > >> > >> > >> For this problem, we will define a solid using a set of points in 3D > >> space. The points define the vertices on the surface of the solid. > >> The edges of the solid are defined as the lines between the points. > >> The faces of the solid are defined by the set of points which are in > the same plane. > >> In the general case, the faces of the solid's surface can be made as > >> numerous and as small as required, to form the required shape. > >> > >> > >> Our solids will be defined in a 3 dimensional space, with points in > >> the space represented by an x,y,z triple. Thus a solid tetrahedron > >> can be represented by four points in the space. > >> > >> > >> The four points 0,0,0 100,0,0 0,100,0 and 0,0,100 define a simple > >> right tetrahedron. This will be the first solid that we want to print > > >> with our 3D printer. > >> > >> > >> We define a horizontal scan surface for our printer as the plane > >> defined by the three points 0,0,0 100,0,0 0,100,0. There is no > >> reason to define the scan surface array any larger than the solid > >> itself, so the scan surface array can be a 100 x 100-point binary > array. > >> > >> > >> Each point in a scan-surface array must indicate whether it is inside > > >> or outside the solid shape. If the point is inside the solid, a > >> binary one will tell the printer to deposit material at this point. > >> If the point is outside the solid, a binary zero will tell the > >> printer to not deposit any material there. > >> > >> > >> For our 3D printer, we need to generate 100 of these binary scan > >> surface arrays, one for each resolution step as the printer moves up > >> through the solid space. These 100 scan surface arrays define where > >> the 3D printer will deposit material on each layer, to form our > >> tetrahedron. The 3D printer will start with the lowest layer of the > >> scan arrays, and build the material up from there. > >> > >> > >> The problem is to define a J verb that will generate the one hundred > >> 100x100 2D binary arrays (essentially building a 100x100x100 3D > >> binary matrix), which represents the 100 horizontal slices through > >> the solid. That binary matrix will indicate to the 3D printer where > >> to place the material to create the solid. > >> > >> > >> Once you have generated the 100x100x100 binary array for the > >> tetrahedron, test your function out by generating a similar scan > >> surface array for the solid created by the intersection of two > tetrahedrons: > >> > >> > >> Tetrahedron 1: 50,0,0 0,50,0 50,50,0 25,25,100 > >> > >> Tetrahedron2: 0,50,0 0,0,50 0,50,50 100,25,25 > >> > >> > >> For further challenges, see if your J function can generate the set > >> of 3D printer scan surface arrays for the four other Platonic solids > >> besides the tetrahedron. Here are the J definitions for all the > Platonic solids: > >> http://tinyurl.com/bry2yxc You probably will want to scale these > >> solids up by a factor of 10 or so. > >> > >> > >> In general, your J function should be able to generate binary scan > >> surface arrays for a 3D printer given any arbitrary solid, defined by > > >> a set of points in 3-space. Actually, besides the points, for complex > > >> solids you may need a vector indicating which side of each surface or > > >> face is the inside of the solid. > >> > >> > >> Skip > >> > >> > >> > > > > > > -- > > Skip Cave > > Cave Consulting LLC > > Phone: 214-460-4861 > > > > > > > -- > Skip Cave > Cave Consulting LLC > Phone: 214-460-4861 > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > -- Skip Cave Cave Consulting LLC Phone: 214-460-4861 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
