Comparison of Free scripted 3D CAD systems, part 2
==================================================

Werner Almesberger <werner@almesberger.net>

This is the continuation of my evaluation of scripted 3D CAD systems.
It shows new findings and improvements since the last test.


Introduction
============

This file and the sources of the models can be found in
http://projects.qi-hardware.com/index.php/p/wernermisc/source/tree/master/cad/test2/


New findings and hypotheses
===========================

The first test revealed several problems in both OpenSCAD and
Cadmium. It turned out that most of them could be resolved by making
small changes to the models.


The road to hell is paved with good intentions
----------------------------------------------

The original model tried to prevent the creation of artefacts through
rounding errors. It turned out that this isn't only unnecessary with
Cadmium, but it massively slows down the rendering.

Also, after removing these preventions the bug the "noise" parameter
worked around no longer appeared.

This is a comparison of run time (in seconds) and mesh size:

                real    user    system  faces   vertices
Before:         4901.0  4904.4     1.5  8362    3183
After:           316.3   315.9     0.3  2942    1473

This makes Cadmium only about 4-5 times slower than OpenSCAD's CGAL
rendering, a marked improvement from the previous factor of 57. The
resulting mesh is now less than half the size of the mesh generated
by OpenSCAD.

Furthermore, the model is much easier to design and more
understandable without these extra tolerances.


Background: preventing artefacts
--------------------------------

When subtracting volumes from each other, surfaces that coincide in
both the original volume and the one subtracted from it can remain
as arbitrarily thin artefacts.

This 2D example illustrates the effect:

- given an original shape like this

  +---------------+
  |               |
  |               |
  |               |
  |               |
  |               |
  +---------------+

- we want to subtract the following shape from it:

         +--------+
         |        |
         +--------+
 
- expecting this to result in something like

  +---------------+
  |               |
  |      +--------+
  |      |
  |      +--------+
  |               |
  +---------------+

- however, if the subtraction isn't perfectly exact, we may get this
  instead:

  +---------------+
  |               |
  |      +--------+
  |      |        |<--- very thin surface
  |      +---^----+
  |          |    |
  +----------|----+
             |
          empty space

- to avoid this problem, we could enlarge the shape that is
  subtracted:

         +---------+
         |         |
         +---------+


Artefacts in OpenSCAD's mesh were rounding errors
-------------------------------------------------

The artefacts found in the mesh produced by OpenSCAD were also caused
by rounding errors. In this case, the problem were parts that were
fused along a common surface. As in the above example, this could be
solved by making the parts overlap a little.

This change affected the rendering performance as follows:

                real    user    system  faces   vertices
Before:		  85.5	  85.0	   0.4	7798	3351
After:		  68.8	  65.4	   0.5	6508	3258

The resulting mesh looks as good as the one generated by Cadmium.


OpenCSG problems may be an OpenGL compatibility issue
-----------------------------------------------------

It could be that OpenCSG showing volumes to be removed just with a
different color without actually removing them is caused by using
OpenGL emulation in Mesa. This needs further investigation.


Conclusion
==========

The model used in the first test contained constructs that were meant
to help avoid ambiguous situations. It turned out that Cadmium did
not need this "help" and removing the constructs substantially
increased the rendering speed.

OpenSCAD is the exact opposite: it produces clearly visible
artefacts in ambiguous cases and rendering speed also benefits from
manual resolution of these issues. The cost of doing so is an
increase of the complexity of the model.

Performance after the model changes (times are in seconds):

                real    user    system  faces   vertices
OpenSCAD:	  68.8	  65.4	   0.5	6508	3258
Cadmium:	 316.3	 315.9	   0.3	2942	1473

The sources of the models used are in
http://projects.qi-hardware.com/index.php/p/wernermisc/source/tree/master/cad/test2/

The meshes can be downloaded from
http://downloads.qi-hardware.com/people/werner/cad/test2/

---------------------------------------------------------------------
