New to Panda and absolutely loving it Made more progress in 2 days than I have in 3 months with Blender Game Engine, Darkbasic, and Adobe Director.
Does anybody have any code that will take a text file with a series of x y z coordinates and convert it into an egg 3d mesh?
There’s a whole load of commercial stuff that converts 3d laser scanner and topographic data into meshes but it’s very expensive. I’ve also found some code that does 3d delaunay triangulation but I could not make sense of it.
I’m building a virtual radiotherapy treatment machine and I need to take the outline of patients and make it into a mesh to include in the simulation.
Is your data set really a set of random points? Most scanning equipment does not output random points - there is usually a scanning pattern, such as a plane or cylinder depending on what the scanning head does, which can make stitching it together very easy if you know that structure.
But your right to be looking at 3D Delaunay triangulations - that is the way to go. My only advice there is to go look at a 2D version - cs.cornell.edu/home/chew/Delaunay.html That link has a java applet thing going for 2D - playing with it should give you an idea of how it works, and how it helps you find a suitable boundary. Actual code does get quite fiddly though, 'fraid I don’t have code that is going to be any easier than what you have already found.
I’d second this. Usually scan data is acquired on a rough 2D grid that corresponds to the camera sensor (and the sweep of the laser line over time, for a laser scanner). Usually this means that in addition to the true 3D coords of each point there is a 2D integer coord.
What you can do with this is create a 2D array of points which is very easy to triangulate. Don’t worry about anything as complex as Delaunay, at least at first, just create triangles anywhere there are 3 or 4 points in a 2x2 section of the complete grid. This is the method that many scanners that use interactive preview software will use to generate the initial meshes, and is also what mesh merging software like Polyworks will generate.
At this point it should be trivial to convert the triangles into an egg. Things will get much more complicated if you ever have to align multiple scans and merge them into a single mesh, though. I’ve written software that can do this sort of thing (sorry, not open source), and there’s a reason why software like Polyworks costs a fair amount, because it’s tricky to do well.
Point data is arranged in slices, with points in an orderly clockwise progression round the outline. But the number of points in each slice is different, so I don’t know how to create the triangles between the slices.
upload the data set and i’ll give you en egg if its not to hard! I love large scale data manipulations!
The algorithm I would use is connect all closes point pairs together. Then keep connecting till you are at a “good stopping” point. Then draw triangles starting between two shortest lines and up. Stop when every thing is filled in.
Well, that certainly makes the problem easier. There is no right way of solving that problem I expect (i.e. different base assumptions lead to different solutions). However, assuming you can sort the points in each slice along the axis of the scanning cylinder what I would do is:
For each pair of slices that need stitching together:
Select one side, for each line segment in that side select the point that makes the resulting triangle closest to isosceles, i.e. interpolate to the middle of the slice to find a coordinate and find the closest point to that point in the other slice.
You then need to fill in the other sides triangles with triangle fans to finish the strip - this can be done by again iterating the line segments, where in most cases you can share edges with the triangles that already exist.
That is probably a bit convoluted - not sure it even makes sense to me. And you do need to make sure triangles don’t overlap, but as there ordered keeping track of the last one used will work there. But hopefully it will give you enough of an idea for you to fill in the gaps!
P.S. If you do need some software to stitch together multiple scans then scanalyze is rather obscure but open source, and has been used for real work so I presume it works, even though I have never used it myself. Find it at graphics.stanford.edu/software/scanalyze/