Optimized view map calculation by Alexander Beels.

* View map calculation has been intensively optimized for speed by
means of:

1) new spatial grid data structures (SphericalGrid for perspective
cameras and BoxGrid for orthographic cameras; automatically switched
based on the camera type);

2) a heuristic grid density calculation algorithm; and

3) new line visibility computation algorithms: A "traditional"
algorithm for emulating old visibility algorithms, and a "cumulative"
algorithm for improved, more consistent line visibility, both exploiting
the new spatial grid data structures for fast ray casting.

A new option "Raycasting Algorithm" was added to allow users to choose
a ray casting (line visibility) algorithm.  Available choices are:

- Normal Ray Casting
- Fast Ray Casting
- Very Fast Ray Casting
- Culled Traditional Visibility Detection
- Unculled Traditional Visibility Detection
- Culled Cumulative Visibility Detection
- Unculled Cumulative Visibility Detection

The first three algorithms are those available in the original
Freestyle (the "normal" ray casting was used unconditionally, though).
The "fast" and "very fast" ray casting algorithms achieve a faster
calculation at the cost of less visibility accuracy.

The last four are newly introduced optimized options.  The culled
versions of the new algorithms will exclude from visibility
calculation those faces that lay outside the camera, which leads to a
faster view map construction.  The unculled counterparts will take all
faces into account.  The unculled visibility algorithms are useful
when culling affects stroke chaining.

The recommended options for users are the culled/unculled cumulative
visibility algorithms.  These options are meant to replace the old
algorithms in the future.

Performance improvements over the old algorithms depend on the scenes
to be rendered.

* Silhouette detection has also been considerably optimized for speed.

Performance gains by this optimization do not depend on scenes.

* Improper handling of error conditions in the view map construction
was fixed.

1 files changed, 97 insertions, 0 deletions

diff --git a/source/blender/freestyle/intern/system/PointerSequence.h b/source/blender/freestyle/intern/system/PointerSequence.h
new file mode 100644
index 00000000000..72c6aa458fd
--- /dev/null
+++ b/source/blender/freestyle/intern/system/PointerSequence.h
@@ -0,0 +1,97 @@
+//
+//  Filename         : PointerSequence.h
+//  Author(s)        : Alexander Beels
+//  Purpose          : Class to define a cell grid surrounding
+//                     the projected image of a scene
+//  Date of creation : 22/11/2010
+//
+///////////////////////////////////////////////////////////////////////////////
+
+
+//
+//  Copyright (C) : Please refer to the COPYRIGHT file distributed 
+//   with this source distribution. 
+//
+//  This program is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU General Public License
+//  as published by the Free Software Foundation; either version 2
+//  of the License, or (at your option) any later version.
+//
+//  This program is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+//  GNU General Public License for more details.
+//
+//  You should have received a copy of the GNU General Public License
+//  along with this program; if not, write to the Free Software
+//  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+//
+// Simple RAII wrappers for std:: sequential containers
+//
+///////////////////////////////////////////////////////////////////////////////
+
+//
+// PointerSequence
+//
+// Produces a wrapped version of a sequence type (std::vector, std::deque, std::list)
+// that will take ownership of pointers tht it stores.  Those pointers will be deleted
+// in its destructor.
+//
+// Because the contained pointers are wholly owned by the sequence, you cannot make a
+// copy of the sequence.  Making a copy would result in a double free.
+//
+// This is a no-frills class that provides no additional facilities.  The user is
+// responsible for managing any pointers that are removed from the list, and for making 
+// sure that any pointers contained in the class are not deleted elsewhere.  Because 
+// this class does no reference counting, the user must also make sure that any pointer
+// appears only once in the sequence.
+//
+// If more sophisticated facilities are needed, use tr1::shared_ptr or boost::shared_ptr.
+// This class is only intended to allow one to eke by in projects where tr1 or boost are
+// not available.
+//
+// Usage: The template takes two parameters, the standard container, and the class held
+// in the container.  This is a limitation of C++ templates, where T::iterator is not a
+// type when T is a template parameter.  If anyone knows a way around this
+// limitation, then the second parameter can be eliminated.
+//
+// Example:
+//   PointerSequence<vector<Widget*>, Widget*> v;
+//   v.push_back(new Widget);
+//   cout << v[0] << endl; // operator[] is provided by std::vector, not by PointerSequence
+//   v.destroy(); // Deletes all pointers in sequence and sets them to NULL.
+//
+// The idiom for removing a pointer from a sequence is:
+//   Widget* w = v[3];
+//   v.erase(v.begin() + 3); // or v[3] = 0;
+// The user is now responsible for disposing of w properly.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef  POINTERSEQUENCE_H
+# define POINTERSEQUENCE_H
+
+#include <algorithm>
+
+template <typename C, typename T>
+class PointerSequence : public C {
+	PointerSequence (PointerSequence& other);
+	PointerSequence& operator= (PointerSequence& other);
+	static void destroyer (T t) {
+		delete t;
+	}
+public:
+	PointerSequence () {};
+	~PointerSequence () {
+		destroy();
+	}
+	void destroy () {
+		for_each (this->begin(), this->end(), destroyer);
+	}
+};
+
+#endif // POINTERSEQUENCE_H
+