the algorithms in the CGAL library might be a good starting point in terms of looking into other algorithmic approaches http://www.cgal.org/ it has a excellent set of references for its component parts On Sun, Jun 5, 2011 at 11:41 AM, Andrew Coppin wrote:

On 04/06/2011 08:25 PM, Tom Hawkins wrote:

What is the easiest way to generate polygon meshes from constructive

...

solid geometry? Marching cubes [4] seems pretty involved.

As I understand it, this is a Very Hard Problem. This is (one of the reasons) why there are so few converters from POV-Ray to mesh-based formats; it's highly non-trivial to tesselate CSG.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

2011/6/5 Tom Hawkins :

On Sun, Jun 5, 2011 at 10:41 AM, Andrew Coppin wrote:

...

On 04/06/2011 08:25 PM, Tom Hawkins wrote:

...

What is the easiest way to generate polygon meshes from constructive solid geometry?  Marching cubes [4] seems pretty involved.

As I understand it, this is a Very Hard Problem. This is (one of the reasons) why there are so few converters from POV-Ray to mesh-based formats; it's highly non-trivial to tesselate CSG.

POV-Ray is pretty fast.  I had contemplated just rendering a bunch of POV-Ray images to emulate a realtime 3D view.  Images could be buffered up based on the current camera position.

Another goal of the project is to generate 2D prints from 3D models. Any idea how hard is this going to be?  Basically it needs to identify features (holes, edges, etc), then project these features to an orthographic plane, alone with associated dimensions.

Once the conversion to triangles (or polygons) is handled, you should be able to import the model into some rendering engine. Orthographic projection isn't more difficult to achieve than perspective projection. You would have to chose the renderer so it comes with the kind of effect you want. (The feature detection you mean such that they are for instance rendered as strokes is a rendering effect, so no need I believe to first detect them then render them. I also believe there are such rendering that are done as a post-effect, on the 2d data (possibly with dept or normal information available)). Don't povray provides such a rendering mode? Otherwise, given a mesh model, idetifying the edges (with no respect to the screen) is quite easy in the principle: make any edge that separates two faces whose normals make an angle above some thresold a hard edge. To take the screen into account, you would have probably to compare the surface normal at the edge and the camera direction. One thing that would be neat for you, but I have no idea if it exists, would be to turn directly the CSG models to 2d vector graphics. Cheers, Thu

...

As I understand it, this is a Very Hard Problem. This is (one of the reasons) why there are so few converters from POV-Ray to mesh-based formats; it's highly non-trivial to tesselate CSG.

POV-Ray is pretty fast. I had contemplated just rendering a bunch of POV-Ray images to emulate a realtime 3D view. Images could be buffered up based on the current camera position.

That's an... interesting way of doing it. It's probably easier to build a simple renderer internal to your program, but I suppose calling POV-Ray gives you lots of functionality without having it to implement it yourself.

Another goal of the project is to generate 2D prints from 3D models. Any idea how hard is this going to be? Basically it needs to identify features (holes, edges, etc), then project these features to an orthographic plane, alone with associated dimensions.

That ought to be reasonably easy. If you think of each shape's surface as being the set of points satisfying an equation, then the edges of the intersection of those shapes would be the set of points satisfying a set of simultanious equations. (Quite possibly non-linear ones, depending on which kinds of shapes you allow.) The only really tricky part is if you want to represent all of these shapes as "simple" curves such as lines, ellipses and paraboliods. See, for example, http://mathworld.wolfram.com/SteinmetzSolid.html "The curves of intersection of two cylinders of radii a and b, shown above, are given by the parametric equations x(t) = b cos t y(t) = b sin t z(t) = +/- Sqrt(a^2 - b^2 sin^2 t) (Gray 1997, p. 204)." A curve like that is not the sort of thing you can easily represent in SVG, unless you turn it into a general spline.