Pierre Dolbeault
email: pierre.dolbeault@upmc.fr

ON A NONCOMMUTATIVE ALGEBRAIC GEOMETRY

Keywords: 2010 Mathematics Subject Classification: Primary 30G35; Secondary 30D30 quaternions, holomorphic, hypermeromorphic functions, Hamilton 4manifolds

Several sets of quaternionic functions are described and studied with respect to hyperholomorphy, addition and (non commutative) multiplication, on open sets of H, then Hamilton 4-manifolds analogous to Riemann surfaces, for H instead of C, are defined, and so begin to describe a class of four dimensional manifolds.

1. Introduction. We first recall the definition of the field H of quaternions using pairs of complex numbers and a modified Cauchy-Fueter operator (section 2) that have been introduced by C. Colombo and al.,[START_REF] Colombo | A new characterization of pseudoconvex domains in C 2[END_REF]. We will only use right multiplication. We will consider C ∞ H-valued quaternionic functions defined on an open set U of H whose behavior mimics the behavior of holomorphic functions on an open set of C. If such a function does not vanish identically, it has an (algebraic) inverse. Finally we describe properties of Hyperholomorphic functions with respect to addition and multiplication.

In section 3, we characterize the quaternionic functions which are, almost everywhere, hyperholomorphic and whose inverses are hyperlomorphic almost everywhere, on U , as the solutions of a system of two non linear PDE. We find non trivial examples of a solution showing that the considered space of functions is significant; we will call these functions Hypermeromorphic.

At the moment, I am unable to get the general solution of the the system of PDE. Same difficulty for subsequent occurring systems of PDE.

In section 4, we describe a subspace of hyperholomorphic and hypermeromorphic functions defined almost everywhere on U , having "good properties for addition and multiplication"; we again obtain systems of non linear PDE.

In section 5 and the following, we consider globalization of the above notions, define Hamilton 4-manifolds analogous to Riemann surfaces, for H instead of C, and give examples of such manifolds; our ultimate aim is to describe a class of 4-dimensional manifolds.

2. Quaternions. H-valued functions. Hyperholomorphic functions. See [START_REF] Colombo | Analysis of Dirac Systems and Computational Algebra[END_REF][START_REF] Colombo | A new characterization of pseudoconvex domains in C 2[END_REF][START_REF] Dolbeault | On quaternionic functions[END_REF].

2.1. Quaternions. If q ∈ H, then q = z 1 + z 2 j where z 1 , z 2 ∈ C. We have z 1 j = jz 1 , and note |q|

= |z 1 | 2 + |z 2 | 2 .
The conjugate of q is q = z 1 -z 2 j. Let us denote * the (right) multiplication in H, then the right inverse of q is: q -1 = |q| -1 q 2.2. Quaternionic functions. Let U be an open set of

H ∼ = C 2 and f ∈ C ∞ (U, H), then f = f 1 + f 2 j, where f 1 , f 2 ∈ C ∞ (U, C).
The complex valued functions f 1 , f 2 will be called the components of f .

Definitions. Let U be an open neighborhood of 0 in

H ∼ = C 2 .
(a) From now on, we will consider the quaternionic functions f = f 1 + f 2 j having the following properties:

(i) When f 1 and f 2 are not holomorphic, the set Z(f 1 ) ∩ Z(f 2 ) is discrete on U ; (ii) for every q ∈ Z(f 1 ) ∩ Z(f 2 ), J α q (.) denoting the jet of order α at q (see [M66]), let m i = sup αi J αi q (f i ) = 0; m i , i = 1, 2, is finite. m q = inf m i is the order of the zeroe q of f . (b) We will also consider the quaternionic functions defined almost everywhere on U (i.e. outside a locally finite set of C ∞ hypersurfaces, namely Z(f 1 ), Z(f 2 )).

2.4. Modified Cauchy-Fueter operator D. Hyperholomorphic functions. See [START_REF] Colombo | A new characterization of pseudoconvex domains in C 2[END_REF][START_REF] Fueter | Über einen Hartogs'schen Satz[END_REF].

For

f ∈ C ∞ (U, H), with f = f 1 + f 2 j, Df (q) = 1 2 ∂ ∂z 1 + j ∂ ∂z 2 f (q). A function f ∈ C ∞ (U, H) is said hyperholomorphic if Df = 0.
Characterization of the hyperholomorphic function f on U :

∂f 1 ∂z 1 - ∂f 2 ∂z 2 = 0; ∂f 1 ∂z 2 + ∂f 2 ∂z 1 = 0, on U.
(1) 2.5. Several families of meromorphic functions. The conditions f 1 is holomorphic and f 2 is holomorphic are equivalent on U ; the same is true for almost everywhere defined holomorphic functions on U . By definition, holomorphic (almost everywhere defined functions of two complex variables on U are such that f 2 = 0, and f 1 is (almost everywhere) holomorphic.

2.5.1. Consider the almost everywhere defined hyperholomorphic functions on U whose components are real.

f = f 1 + f 2 j
According to a remark of Guy Roos in March 2013, they are almost everywhere holomorphic [R13].

2.5.2. The above considered almost everywhere holomorphic functions are meromorphic and constitute two H-commutative algebras A 1 , A 2 , with common origin 0. Let f = a+bi, and g = c+dj, with a, b, c, d ∈ R be two almost everywhere defined holomorphic functions i.e.meromorphic functions on U .

A 1 is the set of the meromorphic functions f = a+bi, and A 2 is the set of meromorphic functions g = c + dj, with a, b, c, d ∈ R

The sums f + g = a + c + dj + bi constitute the algebra A 1 + A 2 of meromorphic functions.

More generally, A α,β = αA 1 + βA 2 , with α, β ∈ R is an algebra of meromorphic functions on U .

A αβ = a,b,c,d,α,β∈R α(a + bi) + β(c + dj) 2.5.3. We now begin to introduce multiplication for hyperholomorphic functions, addition and scalar muliplication being obvious.

2.6. Multiplication of almost everywhere defined hyperholomorphic functions.

Proposition 2.1. Let f ′ , f ′′ be two almost everywhere defined hyperholomorphic functions. Then, their product f ′ * f ′′ satisfies:

D(f ′ * f ′′ ) = Df ′ * jf ′′ + f ′ ( ∂ ∂z 1 ) + f ′ j ∂ ∂z 2 f ′′ Proof. f ′ = f ′ 1 + f ′ 2 j, f ′′ = f ′′ 1 + f ′′ 2 j be two hyperholomorphic functions.
We have:

f ′ * f ′′ = (f ′ 1 + f ′ 2 j)(f ′′ 1 + f ′′ 2 j) = f ′ 1 f ′′ 1 -f ′ 2 f ′′ 2 + (f ′ 1 f ′′ 2 + f ′ 2 f ′′ 1 )j Compute 1 2 ∂ ∂z 1 + j ∂ ∂z 2 f ′ 1 f ′′ 1 -f ′ 2 f ′′ 2 + (f ′ 1 f ′′ 2 + f ′ 2 f ′′ 1 )j
By derivation of the first factors of the sum f ′ * f ′′ , we get the first term:

1 2 ∂f ′ 1 ∂z 1 + j ∂f ′ 1 ∂z 2 (f ′′ 1 + f ′′ 2 j) + 1 2 ∂f ′ 2 ∂z 1 + j ∂f ′ 2 ∂z 2 jj(f ′′ 2 -f ′′ 1 j) = 1 2 ∂f ′ 1 ∂z 1 + j ∂f ′ 1 ∂z 2 (f ′′ 1 + f ′′ 2 j) + 1 2 ∂f ′ 2 j ∂z 1 + j ∂f ′ 2 j ∂z 2 j(f ′′ 2 j + f ′′ 1 ) = Df ′ * jf ′′ By derivation in 1 2 ∂ ∂z 1 + j ∂ ∂z 2 f ′ 1 f ′′ 1 + f ′ 2 jf ′′ 2 j + (f ′ 1 f ′′ 2 j + f ′ 2 jf ′′ 1 )
of the second factors of the sum f ′ * f ′′ , we get the second term (up to factor 1 2 ):

f ′ 1 ∂f ′′ 1 ∂z 1 + f ′ 1 j ∂f ′′ 1 ∂z 2 + f ′ 1 ∂f ′′ 2 ∂z 1 j + f ′ 1 j ∂f ′′ 2 ∂z 2 j + f ′ 2 j ∂f ′′ 2 ∂z 1 j + f ′ 2 j ∂f ′′ 2 ∂z 2 + f ′ 2 j ∂f ′′ 1 ∂z 1 + f ′ 2 jj ∂f ′′ 1 ∂z 2 = (f ′ 1 + f ′ 2 j)( ∂ ∂z 1 )(f ′′ 1 + f ′′ 2 j) + (f ′ 1 + f ′ 2 j)j ∂ ∂z 2 (f ′′ 1 + f ′′ 2 j) = (f ′ 1 + f ′ 2 j)( ∂ ∂z 1 ) + (f ′ 1 + f ′ 2 j)j ∂ ∂z 2 (f ′′ 1 + f ′′ 2 j) = f ′ ( ∂ ∂z 1 ) + f ′ j ∂ ∂z 2 f ′′ .
3. Almost everywhere hyperholomorphic functions whose inverses are almost everywhere hyperholomorphic.

3.1. Definitions. We call inverse of a quaternionic function f : q → f (q), the function defined almost everywhere on U : q → f (q) -1 ; then:

f -1 = |f | -1 f , where f is the (quaternionic) conjugate of f , then: f -1 = |f | -1 (f 1 -f 2 j). Behavior of f -1 at q ∈ Z(f ). Let n 1 = supJ α q (|f |f -1 1 ); n 2 = supJ α q (|f |f - 1
2 ). Define : n q = sup n i , i = 1, 2 as the order of the pole q of f -1 .

Characterisation.

Proposition 3.1. The following conditions are equivalent:

(i) the function f and its right inverse are hyperholomorphic, when they are defined;

(ii) we have the equations:

(f 1 -f 1 ) ∂f 1 ∂z 1 -f 2 ∂f 2 ∂z 1 -f 2 ∂f 1 ∂z 2 = 0 f 2 ∂f 1 ∂z 1 + ∂f 2 ∂z 1 (f 1 -f 1 ) -f 2 ∂f 2 ∂z 2 = 0 Proof. Let f = f 1 +f 2 j be a hyperholomorphic function and g = g 1 +g 2 j = |f | -1 (f 1 -f 2 j) its inverse; so g 1 = |f | -1 f 1 ; g 2 = -|f | -1 f 2 , where |f | = (f 1 f 1 + f 2 f 2 ). Dg(q) = 1 2 ∂ ∂z 1 + j ∂ ∂z 2 g(q) = 1 2 ∂g 1 ∂z 1 - ∂g 2 ∂z 2 (q) + j 1 2 ∂g 1 ∂z 2 + ∂g 2 ∂z 1 (q) ∂g 1 ∂z 1 = |f | -1 ∂f 1 ∂z 1 -|f | -2 f 1 ∂f 1 ∂z 1 f 1 + f 1 ∂f 1 ∂z 1 + ∂f 2 ∂z 1 f 2 + f 2 ∂f 2 ∂z 1 - ∂g 2 ∂z 2 = |f | -1 ∂f 2 ∂z 2 -|f | -2 f 2 ∂f 1 ∂z 2 f 1 + f 1 ∂f 1 ∂z 2 + ∂f 2 ∂z 2 f 2 + f 2 ∂f 2 ∂z 2 ∂g 1 ∂z 2 = |f | -1 ∂f 1 ∂z 2 -|f | -2 f 1 ∂f 1 ∂z 2 f 1 + f 1 ∂f 1 ∂z 2 + ∂f 2 ∂z 2 f 2 + f 2 ∂f 2 ∂z 2 ∂g 2 ∂z 1 = -|f | -1 ∂f 2 ∂z 1 + |f | -2 f 2 ∂f 1 ∂z 1 f 1 + f 1 ∂f 1 ∂z 1 + ∂f 2 ∂z 1 f 2 + f 2 ∂f 2 ∂z 1 2|f | 2 Dg = (f 1 f 1 + f 2 f 2 )( ∂f 1 ∂z 1 + ∂f 2 ∂z 2 ) -f 1 f 1 ∂f 1 ∂z 1 -f 1 f 1 ∂f 1 ∂z 1 -f 1 f 2 ∂f 2 ∂z 1 -f 1 f 2 ∂f 2 ∂z 1 -f 1 f 2 ∂f 1 ∂z 2 -f 1 f 2 ∂f 1 ∂z 2 -f 2 f 2 ∂f 2 ∂z 2 -f 2 f 2 ∂f 2 ∂z 2 +j (f 1 f 1 + f 2 f 2 )( ∂f 1 ∂z 2 - ∂f 2 ∂z 1 ) -f 1 f 1 ∂f 1 ∂z 2 -f 1 f 1 ∂f 1 ∂z 2 -f 1 f 2 ∂f 2 ∂z 2 -f 1 f 2 ∂f 2 ∂z 2 +f 1 f 2 ∂f 1 ∂z 1 + f 1 f 2 ∂f 1 ∂z 1 + f 2 f 2 ∂f 2 ∂z 1 + f 2 f 2 ∂f 2 ∂z 1 Use the fact: f is hyperholomorphic: (1) ∂f 1 ∂z 1 - ∂f 2 ∂z 2 = 0; ∂f 1 ∂z 2 + ∂f 2 ∂z 1 = 0 2|f | 2 Dg = f 1 f 1 ∂f 2 ∂z 2 + f 2 f 2 ∂f 1 ∂z 1 -f 1 f 1 ∂f 1 ∂z 1 -f 1 f 2 ∂f 2 ∂z 1 -f 1 f 2 ∂f 1 ∂z 2 -f 2 f 2 ∂f 2 ∂z 2 + f 2 ∂f 2 ∂z 1 (f 1 -f 1 )+ +j +f 2 f 2 ∂f 1 ∂z 2 -f 1 f 2 ∂f 2 ∂z 2 -f 1 f 2 ∂f 2 ∂z 2 +f 1 ∂f 1 ∂z 2 (f 1 -f 1 )+f 1 f 2 ∂f 1 ∂z 1 +f 1 f 2 ∂f 1 ∂z 1 +f 2 f 2 ∂f 2 ∂z 1
f being hyperholomorphic, g hyperholomorphic is equivalent to the system of two equations:

+f 1 f 1 ∂f 2 ∂z 2 + f 2 f 2 ∂f 1 ∂z 1 -f 1 f 1 ∂f 1 ∂z 1 -f 1 f 2 ∂f 2 ∂z 1 -f 1 f 2 ∂f 1 ∂z 2 -f 2 f 2 ∂f 2 ∂z 2 + f 2 ∂f 2 ∂z 1 (f 1 -f 1 ) = 0 +f 2 f 2 ∂f 1 ∂z 2 -f 1 f 2 ∂f 2 ∂z 2 -f 1 f 2 ∂f 2 ∂z 2 + f 1 ∂f 1 ∂z 2 (f 1 -f 1 ) + f 1 f 2 ∂f 1 ∂z 1 + f 1 f 2 ∂f 1 ∂z 1 + f 2 f 2 ∂f ∂z = 0
f 1 and f 2 satisfy, by conjugation of the second equation:

+f 2 f 2 ∂f 1 ∂z 1 -f 1 f 1 ∂f 1 ∂z 1 -f 1 f 2 ∂f 2 ∂z 1 + f 2 ∂f 2 ∂z 1 (f 1 -f 1 ) + f 1 f 1 ∂f 2 ∂z 2 -f 1 f 2 ∂f 1 ∂z 2 -f 2 f 2 ∂f ∂z = 0 +f 1 f 2 ∂f 1 ∂z 1 + f 1 f 2 ∂f 1 ∂z 1 . + f 2 f 2 ∂f 2 ∂z 1 + f 2 f 2 ∂f 1 ∂z 2 -f 1 f 2 ∂f 2 ∂z 2 -f 1 f 2 ∂f 2 ∂z 2 + f 1 ∂f 1 ∂z 2 (f 1 -f 1 ) = 0
Using (1), we get:

+f 2 f 2 ∂f 1 ∂z 1 + f 1 (f 1 -f 1 ) ∂f 1 ∂z 1 -f 1 f 2 ∂f 2 ∂z 1 + f 2 ∂f 2 ∂z 1 (f 1 -f 1 ) -f 1 f 2 ∂f ∂z -f 2 f 2 ∂f 2 ∂z 2 = 0 +f 1 f 2 ∂f 1 ∂z 1 + (f 1 -f 1 )f 2 ∂f 1 ∂z 1 + f 2 f 2 ∂f 2 ∂z 1 + f 1 ∂f 1 ∂z 2 (f 1 -f 1 ) + f 2 f 2 ∂f ∂z . -f 1 f 2 ∂f 2 ∂z 2 = 0 Assume f 1 = 0, f 2 = 0 f 1 f 2 f 2 ∂f 1 ∂z 1 + f 1 (f 1 -f 1 ) ∂f 1 ∂z 1 -f 1 f 2 ∂f 2 ∂z 1 + f 2 ∂f 2 ∂z 1 (f 1 -f 1 ) -f 1 f 2 ∂f 1 ∂z 2 -f 2 f 2 ∂f 2 ∂z 2 = 0 -f 2 +f 1 f 2 ∂f 1 ∂z 1 +(f 1 -f 1 )f 2 ∂f 1 ∂z 1 +f 2 f 2 ∂f 2 ∂z 1 -f 1 ∂f 2 ∂z 1 (f 1 -f 1 )+f 2 f 2 ∂f ∂z -f 1 f 2 ∂f 2 ∂z 2 = 0
By sum:

f 1 f 1 (f 1 -f 1 ) ∂f 1 ∂z 1 -f 1 f 2 ∂f 2 ∂z 1 + f 2 ∂f 2 ∂z 1 (f 1 -f 1 ) -f 1 f 2 ∂f 1 ∂z 2 -f 2 (f 1 -f 1 )f 2 ∂f 1 ∂z 1 + f 2 f 2 ∂f 2 ∂z 1 -f 1 ∂f 2 ∂z 1 (f 1 -f 1 ) + f 2 f 2 ∂f 1 ∂z 2 = 0 i.e. (f 1 f 1 + f 2 f 2 ) (f 1 -f 1 ) ∂f 1 ∂z 1 -f 2 ∂f 2 ∂z 1 -f 2 ∂f 1 ∂z 2 = 0 f 2 f 2 f 2 ∂f 1 ∂z 1 + f 1 (f 1 -f 1 ) ∂f 1 ∂z 1 -f 1 f 2 ∂f 2 ∂z 1 + f 2 ∂f 2 ∂z 1 (f 1 -f 1 ) -f 1 f 2 ∂f 1 ∂z 2 -f 2 f 2 ∂f 2 ∂z 2 = 0 f 1 + f 1 f 2 ∂f 1 ∂z 1 + (f 1 -f 1 )f 2 ∂f 1 ∂z 1 + f 2 f 2 ∂f 2 ∂z 1 -f 1 ∂f 2 ∂z 1 (f 1 -f 1 ) + f 2 f 2 ∂f 1 ∂z 2 -f 1 f 2 ∂f 2 ∂z 2 = 0 By sum f 2 f 2 f 2 ∂f 1 ∂z 1 + f 2 ∂f 2 ∂z 1 (f 1 -f 1 ) -f 2 f 2 ∂f 2 ∂z 2 +f 1 f 1 f 2 ∂f 1 ∂z 1 -f 1 ∂f 2 ∂z 1 (f 1 -f 1 ) -f 1 f 2 ∂f 2 ∂z 2 = 0 i.e. f 2 ∂f 1 ∂z 1 + ∂f 2 ∂z 1 (f 1 -f 1 ) -f 2 ∂f 2 ∂z 2 = 0
3.3. Definition. We will call w-hypermeromorphic function (w-for weak) any almost everywhere defined hyperholomorphic function whose right inverse is hyperholomorphic almost everywhere.

4. On the spaces of hypermeromorphic functions.

4.1. Sum of two w-hypermeromorphic functions.

Proposition 4.1. If f and g are two w-hypermeromorphic functions, then the following conditions are equivalent:

(i) the sum h = f + g is w-hypermeromorphic;

(ii) h satisfies the following PDE:

- ∂|h| ∂z 1 + j ∂|h| ∂z 2 (h 1 -h 2 j) + |h| ∂ ∂z 1 + j ∂ ∂z 2 (h 1 -h 2 j) = 0
Proof. Explicit the condition:

|h| 2 D(h -1 ) = -D(|h)|)(h) + |h|D(h) = 0; with h = h 1 -h 2 j 2Dh = ∂ ∂z 1 + j ∂ ∂z 2 (h 1 -h 2 j) = ∂h 1 ∂z 1 + ∂h 2 ∂z 2 - ∂h 2 ∂z 1 - ∂h 1 ∂z 2 j D(|h|) = D(h 1 h 1 + h 2 h 2 ) = 1 2 ∂ ∂z 1 + j ∂ ∂z 2 (h 1 h 1 + h 2 h 2 ) = 1 2 h 1 ∂h 1 ∂z 1 + h 2 ∂h 2 ∂z 1 + h 1 ∂h 1 ∂z 1 + h 2 ∂h 2 ∂z 1 + 1 2 h 1 ∂h 1 ∂z 2 + h 2 ∂h 2 ∂z 2 + h 1 ∂h 1 ∂z 2 + h 2 ∂h 2 ∂z 2 j = 0.

Product of two w-hypermeromorphic functions.

Proposition 4.2. Let f , g be two w-hypermeromorphic functions on U , then the following conditions are equivalent:

(i) the product f * g is w-hypermeremorphic;

(ii) f and g satisfy the system of PDE:

g 1 ( ∂f 1 ∂z 1 + ∂f 2 ∂z 2 ) + (f 1 -f 1 ) ∂g 1 ∂z 1 + f 2 ∂g 1 ∂z 2 -f 2 ∂g 2 ∂z 1 = 0 g 1 ( ∂f 1 ∂z 2 - ∂f 2 ∂z 1 ) + (f 1 -f 1 ) ∂g 1 ∂z 2 -f 2 ∂g 1 ∂z 1 -f 2 ∂g 2 ∂z 2 = 0
Proof. Let f = f 1 + f 2 j and g = g 1 + g 2 j two hypermeromorphic functions and f * g =

f 1 g 1 -f 2 g 2 + (f 1 g 2 -f 2 g 1 )j their product, then ∂f 1 ∂z 1 - ∂f 2 ∂z 2 = 0; ∂(f 1 g 1 -f 2 g 2 ) ∂z 1 - ∂(f 1 g 2 -f 2 g 1 ) ∂z 2 = g 1 ( ∂f 1 ∂z 1 + ∂f 2 ∂z 2 ) -g 2 ( ∂f 1 ∂z 2 + ∂f 2 ∂z 1 ) + f 1 ∂g 1 ∂z 1 -f 1 ∂g 2 ∂z 2 + f 2 ∂g 1 ∂z 2 -f 2 ∂g 2 ∂z 1 = 0 g 1 ( ∂f 1 ∂z 1 + ∂f 2 ∂z 2 ) + f 1 ∂g 1 ∂z 1 -f 1 ∂g 2 ∂z 2 + f 2 ∂g 1 ∂z 2 -f 2 ∂g 2 ∂z 1 = 0. ∂(f 1 g 1 -f 2 g 2 ) ∂z 2 + ∂(f 1 g 2 -f 2 g 1 ) ∂z 1 = g 1 ( ∂f 1 ∂z 2 - ∂f 2 ∂z 1 ) + g 2 ( ∂f 1 ∂z 1 - ∂f 2 ∂z 2 ) + f 1 ∂g 1 ∂z 2 -f 1 ∂g 2 ∂z 1 + f 2 ∂g 1 ∂z 1 -f 2 ∂g 2 ∂z 2 = 0 g 1 ( ∂f 1 ∂z 2 - ∂f 2 ∂z 1 ) + f 1 ∂g 1 ∂z 2 + f 1 ∂g 2 ∂z 1 -f 2 ∂g 1 ∂z 1 -f 2 ∂g 2 ∂z 2 = 0
4.3. Definition. We will call hypermeromorphic the w-hypermeromorphic functions whose sum and product are w-hypermeromorphic. Their space is nonempty, since it contains the space of the meromorphic functions. Lemma 5.1. The quotient of two pseudoholomorphic functions on U , with the same zeroes and the same orders, is a sha function on U .

Manifolds. The sha functions have been defined on open sets of

H ∼ = C 2 .
Let X be a 4-dimensional manifold bearing an atlas A of charts (h j , U j ) such as the transition functions h i,j : U i ∩ U j → H are sha functions. X = (X, A) will be called an A-manifold analogous for H of a Riemann surface for C. I also propose to call an A-manifold a Hamilton 4-manifold.

5.3. Sheaves of pseudoholomorphic, hypermeromorphic functions.

5.3.1.

Functions on an A-manifold X = (X, A). A map f : X → H is called a pseudoholomorphic function on X, if it is continuous and satisfies the following condition: for every chart (h, U ) of X, (f |U )h -1 : h(U ) → H) is a pseudoholomorphic. In the same way, a map f : X → H is called a hypermeromorphic function on X, if it is continuous and satisfies the following condition:for every chart (h, U ) of X, (f |U )h -1 : h(U ) → H) is a hypermeromorphic.

Examples of Hamilton 4-manifold.

The identity map of H is:

z 1 + z 2 j → z 1 + z 2 j.
Ex. 1: (id H , H) is the unique chart of the atlas defining H as an A-manifold. Proof. The identity map (id

H is f 1 = z 1 , f 2 = z 2 is pseudoholomorphic.
Ex.2: Every open set V of X bears an induced structure of Hamilton 4-manifold.

Ex. 3: Hamilton hypersphere HP.

In the space HxH \ {0}, consider the equivalence relation ρ 1 Rρ 2 : there exists λ ∈ H * = H \ 0 such that ρ 2 = ρ 1 λ (right multiplication by λ). The elements of HxH \ {0} are the pairs (q 1 , q 2 ) = (0, 0). Let π : HxH \ {0} → HxH \ {0} /R denoted HP.

(q 1 , q 2 ) → class of (q 1 , q 2 ) So, HP is the set of the quaternionic lines from the origin of H 2 . Consider the pairs (q 1 , q 2 ) ∈ H 2 , with q 2 = 0 we have: π(q 1 , q 2 ) = π(q 1 q -1 2 , 1); let ζ = q 1 q -1 2 , q 2 = 0; in the same way, consider the pairs (q 1 , q 2 ) ∈ H 2 , with q 1 = 0 we have:

π(q 1 , q 2 ) = π(1, q 2 q -1 1 ); let ζ ′ = q 2 q -1 1 , q 1 = 0. The charts ζ, ζ ′ have for domains U , U ′
, two open sets of HP, respectively homeomorphic to H forming an atlas of HP. Remark that U covers the whole of HP except the point π(q 1 , 0) denoted ∞, and that U ′ covers the whole of HP except the point π(0, q 2 ) denoted 0.

U ′ = HP \ {0}. Over U ∩ U ′ , we have: ζ.ζ ′ = 1, i.e. ζ ′ = ζ -1 and ζ = q 1 q -1 2 . 5.3.3. . Pseudoholomorphic map or morphism.
Let X and Y be two Hamilton 4-manifolds, a map f :

X → Y is said pseudoholomor- phic if it is continuous and if, for every pair of pseudoholomorphic charts (h, U ), (k, V ) such that f (U ) ⊂ V , k(f |U )h -1 : h(U ) → k(V ) be pseudoholomorphic.
5.3.4. Sheaf of pseudoholomorphic functions. Let U, V be two open sets of X such that U ⊂ V , then, the restrictions to U of the pseudoholomorphic functions on V are pseudoholomorphic on U . So is defined the sheaf, denoted P, of (non commutative rings) of pseudoholomorphic functions on X. The pair (X,P) is a ringed space.

In the same way, the sheaf of non commutative rings, denoted M, of hypermeromorphic functions is defined on X. 5.3.5. Hamiltonian Submanifolds. They are submanifolds whose function ring is pseudoholomorphic. We will implicitly use the following fact: If f is a pseudoholomorphic or hypermeromorphic function, the same is true for a + f , where a is any fixed quaternion.

The following examples are complex analytic submanifolds. i) H. Let a be a fixed quaternion, then a + C ⊂ H is a complex line from a embedded in H. ii) HP. Complex projective line imbedded in HP. Let i :

z 1 → z 1 + z 2 j and j : CP → HP C × C \ 0 → H × H \ {0} i × i ↓ ↓ C × C \ 0 /R ′ → H × H \ {0} R
Let p ∈ HP be a fixed point. Then, p + CP 1 is a complex projective line (or Riemann sphere) from p, embedded in HP.

(cf. [D90, ch. 5, 4.1.5]) Let p : Y → X be a morphism of two Hamilton 4-manifolds; p is locally bi-pseudoholomorphic, then it defines, for every y ∈ Y , an isomorphism p y : P x,p(y) → P Y,y ; this defines: p * = p * y = (p * y ) -1 .

6.3. Definition. Let X be a Hamilton 4-manifold, a ∈ X, ϕ

∈ P a . A quadruple (Y, p, f, b) is called an analytic continuation of ϕ if: (i) Y is a Hamilton 4-manifold, p : Y → X is a morphism; (ii) f is a pseudoholomorphic function on Y ; (iii) b ∈ p -1 (a) ⊂ Y ; p * (ρ Y b f ) = ϕ.
An analytic continuation is said to be maximal if it is solution of the following universal map problem: for every analytic continuation (Z, q, g, c) of ϕ, there exists a fibered morphism

F : Z → Y such that F (c) = b and F * (f ) = g. Hence If (Y, p, f, b
) is a maximal analytic continuation of ϕ, it is unique up to an isomorphism. Y is called the Hamilton 4-manifold of ϕ. Theorem 6.3. Let X be a Hamilton 4-manifold, a ∈ X, ϕ ∈ P a . Then there exists a maximal analytic continuation of ϕ.

6.4. Remark. Then, we will say that the above function f is the unique maximal analytic continuation of the germ ϕ. Moreover, the above definitions and results of the section 2 are valid for the sheaf M of hypermeromorphic functions instead of the sheaf P.

Main result.

Theorem 6.4. Let X be a Hamilton 4-manifold and P (T ) = T n + c 1 T n-1 + . . . + c n ∈ M(X)[T ] be an irreducible polynomial of degree n. Then there exist a Hamilton 4-manifold Y , a ramified pseudoholomorphic covering (cf. [D90, ch. 5] for Riemann surfaces) with n leaves Π : Y → X and a hypermeromorphic function F ∈ M(Y ) such that (Π * P )(F ) = 0.

F is the unique maximal analytic continuation of every hypermeromorphic germ ϕ of X such that P (ϕ) = 0; F is called the hyperalgebraic function defined by the polynomial P and Y is the Hamilton 4-manifold of F .

Proof at the end of the section. 1) X is compact connected.

2) Every pseudoholomorphic function on X is constant.

3) Every hypermeromorphic function f on X different from ∞ is rational. 4) In case X = HP, in Theorem 6.4, c j is rational. Indeed, since c j is hypermeromorphic, from 3), it is rational. 6.6. Proof of Theorem 6.4. In the notations of Ex. 3, ζ is a local coordinate on X = HP.

f has a finite set of poles p 1 , . . . , p n . Assume that ∞ is not a pole of f , then p 1 , . . . , p n ∈ H. Let h ν the principal part of f at p ν , then f -h ν = a ν , constant, from 2) and h V j where the V j are disjoint and Π|V j : V j → U is bi-pseudoholomorphic, (j = 1, . . . , n); let ϕ j : U → V j the reverse (i.e. set inverse) of Π|V j and f j = ϕ * j f = f.ϕ j . Then:

ν = -1 j=-kν C νj (ζ -p j ν )
Π n j=1 (T -f j ) = T n + c 1 T n-1 + . . . + c n ; c j = (-1) j s j (f 1 , . . . , f n )
, where s j is the j-th elementary symmetric function in n variables. The c j are hypermeromorphic, locally defined, but glue together into c 1 , . . . , c n ∈ M(X) and are called the elementary symmetric functions of f with respect to Π. 6.6.2. Remark. The elementary symmetric functions of a hypermeromorphic function on Y are still defined when the covering Π is ramified. 6.6.3. . Theorem 6.5. Let Π as in Theorem 6.4, with Y not necessarily connected, A ⊂ X be a discreet closed subset containing all the critical values of Π, and B = Π -1 (A).

Let f be a pseudoholomorphic (resp. hypermeromorphic) function on Y \ B and c 1 , . . . , c n ∈ H(X \ A)(resp.M(X \ A))

the elementary symmetric functions of f . Then the following two conditions are equivalent:

(i) f has a pseudoholomorphic (resp. hypermeromorphic) extension to Y ;

(ii) for every j = 1, . . . , n, c j has a pseudoholomorphic (resp. hypermeromorphic) extension to X. 6.6.4. Existence of Y in Theorem 6.4. Let ∆ ∈ M(X) be the discriminant of P (T ); P (T ) being irreducible, ∆ = 0: then there exists a discrete closed set A ⊂ X such that, for every x ∈ X ′ = X \ A, ∆(x) = 0, and all the functions c j are pseudoholomorphic.

Let Y ′ = {ϕ ∈ H x , x ∈ X ′ ; P (ϕ) = 0} ⊂ LH, etal space defined by the sheaf H, and Π ′ : Y ′ → X, (ϕ → x).

It can be shown that, for every x ∈ X ′ , there exists an open neighborhood U of x in X ′ and functions f j ∈ H(U ), j = 1, . . . , n, such that P (T )|U = Π n j=1 (T -f j ); then Π ′-1 (U ) = [U, f j ] → U is a homeomorphism; Y ′ is a Hamilton 2-manifold non necessarily connected, and a pseudoholomorphic, non ramified covering of X ′ . It can be shown that Π ′ can be extended into a ramified pseudoholomorphic covering Π : Y → X of X for which Y ′ = Π -1 (X ′ ). The c j are defined on the whole of X; from Theorem 6.5, f has an extension F ∈ M(X) such that Π * P (F ) = F n + (Π * c 1 )F n-1 + . . . + Π * c n = 0.

It is easy to prove the connectedness of Y and the unicity of F . This ends the proof of Theorem 6.4. Y is of real dimension 4; Y is connected; Y is compact; Y is C ∞ ; let m be the number of the critical values of Π and q j these critical values; they define points of Y forming the 0-skeleton of a simplicial complex K carried by the manifold Y . K may be supposed to be C ∞ by parts. Cutting along the 3-faces of K defines a fundamental domain F D of the covering Π. F D is a 4-dim polytope in HP with an even number of 3-faces; gluying together the opposite 3-faces, we get a compact 4-dim polytope with homology of the Hamilton 4-manifold Y . 7.2. Homology of Y . H p (Y ; Z), for p = 0, . . . , 4 have to be evaluated, using the critical values q j , and the Poincaré duality.

  The hypermeromorphic functions on a relatively compact open set U of H play the part of the meromorphic functions on a relatively compact open set U of C. We will call pseudoholomorphic function on U , every hypermeromorphic function, without poles on U . We will call smooth hypermeromorphic function (sha function) on U , every hypermeromorphic function, without zeroes and poles on U .

  f j ] where [U, f j ] = {f jy , y ∈ U } is an open set of LH and Π ′ |[U, f j ] :

  7. The Hamilton 4-manifold Y of F when X = HP.7.1. Recall the main properties of Y .

  is a hypermeromorphic function, where C νj ∈ H. 6.6.1. Elementary symmetric functions. Let Π : Y → X be a nonramified pseudoholomorphic covering with n leaves, and f be a hypermeromorphic function on Y . Every point x ∈ X has an open neighborhood U such that

	n
	Π -1 (U ) =
	j=1

iii) Let S be a compact Riemann surface contained in HP as a Hamiltonian submanifold. Then p + S is a compact Riemann surface from p, embedded in HP. 5.3.6. A family of complex submanifolds in a Hamilton 4-manifold. We now use the properties and notions of subsection 2.5.2. They are a + A α,β and also for restrtictions to an open set U of H.

On a Hamilton 4-manifold X with an atlas A and every domain of chart U as above, we obtain: Proposition 5.2. Let (X, P) be a Hamilton 4-manifold. There exist a family of complex analytic curves C b,γ,δ , of X. For every U domain of coordinates in A let A γ,δ . By gluing, we get a complex analytic curve in (X, P) from b ∈ X, and γ, δ are real parameters.

Proof. Let b ∈ X; β, γ ∈ R be given, consider an atlas A whose domains of charts are either open sets

The restrictions of the charts of A to the U ∪ (A β,γ ∩ U ) define an atlas of C b,γ,δ as complex analytic subvariety of (X, P), in the following way: assume b ∈ V β,γ ∩ A β,γ ∩ U and consider the open sets analogous to V β,γ such that the various V β,γ be connected. Then the corresponding A β,γ ∩ U constitute a covering of the unique complex analytic curve C b,γ,δ . 5.3.7. . Let C be a complex analytic curve embedded into X and an atlas A such that every chart of domain U meeting C satisfies: U ∩ C is connected Theorem 5.3. The set of complex analytic curves in X is the family C b,γ,δ .

6. Hamilton 4-manifold of a hypermeromorphic function.

6.1. Analytic continuation along a path. [D90, p. 116] Let X be a Hamilton 4-manifold, γ : [0, 1] → X a continuous path from a to b, ϕ ∈ P a a germ of pseudoholomorphic function at a.

Let τ ∈ [0, 1] and ϕ τ ∈ P γ(τ ) , there exists an open neighborhood U τ of γ(τ ) in X and a pseudoholomorphic function

6.2. Definition. A germ ψ ∈ P b is said to be the analytic continuation of ϕ along γ if there exists a family (ϕ t ) t∈[0,1] such that:

1) ϕ 0 = ϕ and ϕ 1 = ψ.

2) for every τ ∈ [0, 1], for every t ∈ W τ , we have: ρ Uτ γ(τ ) f τ = ϕ τ Theorem 6.1. Identity theorem. Let X be a connected Hamilton 4-manifold and f 1 , f 2 : X → Y be two morphisms which coincide in the neighborhood of a point x 0 ∈ X, then f 1 , f 2 coincide on X.

Proof as for Riemann surfaces, [D90, ch. 5]. Theorem 6.2. Let X be a simply connected Hamilton 4-manifold, a ∈ X, ϕ ∈ P a be a germ having an analytic continuation along every path from a. Then there exists a unique function f ∈ P(X) such that ρ X a f = ϕ.


Jérémie Dumas

Jean Hergel

Sylvain Lefebvre

Bridging the Gap: Automated Steady Scaffoldings for 3D Printing

Keywords: CR Categories: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling; I.3.8 [Computer Graphics]: Applications FDM, FFF, 3D Printing, Scaffoldings, Supports

Figure 1: The upper leg of the Poppy robot (www.poppy-project.org) cannot be 3D printed on low cost FDM printers without support. Our technique automatically generates scaffoldings made of horizontal bridges supported by vertical pillars, shown in purple. The print is shown in the middle and on the right after clean up. Bridges are strong and stable, increasing the print reliability while having a low material usage.

Introduction

Fused filament fabrication (FFF) is a popular technique for turning 3D models into real, tangible objects. A hot filament is melted through a heated nozzle and fuses with the part just below, adding a layer of material to the object being formed. Advantages are the low cost of both printers and filaments, the relative ease of use requiring few manual steps before and after printing, and the wide availability of printers which can be bought from a variety of manufacturers, e.g. Ultimaker, RepRapPro, 3D Systems, Stratasys.

A major drawback of the process, however, is that filament can only be deposited on top of an existing surface. Therefore, overhangs require a disposable structure to be printed, temporarily supporting the threads of plastic that would otherwise hang in empty space. Most of the existing approaches build very reliable support structures that unfortunately incur a large increase in used material and print time. Other approaches produce small support structures but rely on the user to fix an initial, incomplete automated solution. This trial-and-error process often requires multiple test prints. We discuss previous work Section 2.

We design our supports to answer two main criteria: 1) supporting plastic threads wherever necessary, while being easy to remove and 2) minimizing used material, while printing reliably. Material usage and reliability are contradictory goals: as the size of the support is decreased it becomes more delicate to print and mechanically fragile. In particular the weight of the object and the friction of the printing nozzle start to endanger the integrity of the structure. Support generation techniques focus on the issue of overhangs. This is, however, not the only situation in which support is required. Many objects are printed in a fragile equilibrium, or will have subparts in fragile equilibrium at a stage of the printing process. When support is required this issue propagates throughout the entire support structure: a thin support has to be strong enough to support the weight imbalance of the subparts being printed above it. Our supports ensure that not only all overhangs are properly supported, but also that at all stages of the print process the already printed subparts of the object are maintained in a stable position.

Our structures are inspired from the scaffoldings used in construction. In particular, we exploit bridges -horizontal bars printed between mostly vertical pillars. Such bridges can be printed reliably by FFF printers over gaps of several centimeters. These bridges exhibit good mechanical properties and can support other layers of scaffolding. As illustrated in the inset, our scaffoldings are surprisingly strong -this particular scaffolding is made of the same geometry as the scaffoldings we use to support our prints. Despite bridges that are only two threads wide (0.8mm) and two layers thick (0.4mm), it withstands the 83 grams of a coffee cup -the rough equivalent of 35 meters of 1.75mm ABS plastic filament -most objects use less than 10 meters of filament and are supported by several bridges. The scaffolding weights 0.5g. These good mechanical properties led us to a scheme where we only consider the topology of the structure: in all practical cases we encountered and despite printing at the smallest thicknesses ensuring reliability, our bridge structures proved sturdy enough.

Contributions. Our first contribution, described Section 4, is a novel way to select points to be supported based not only on overhangs but also on the stability of the printed model throughout the entire build process. Our second contribution, described Section 5, is an efficient algorithm to build bridge scaffoldings that support a given sets of points in space. The structure itself preserves the balance of the print, while using little material. A major difficulty in computing the structure stems from the constraints ensuring that the result is printable: A bridge may only be printed if it is supported by a pillar in each of its extremities.

Related Work

Determining support requirements. Support generation algorithms start by a determination of the surfaces in need for support. A first family of approaches consider the down-facing facets of the input mesh having an angle too steep to print correctly (e.g. [START_REF] Allen | Determination and evaluation of support structures in layered manufacturing[END_REF][START_REF] Alexander | Part orientation and build cost determination in layered manufacturing[END_REF]). A second family of approaches consist in performing a boolean difference between two successive slices (e.g. [START_REF] Allison | Boolean layer comparison slice[END_REF][START_REF] Chalasani | Support generation for fused deposition modeling[END_REF]Huang et al. 2009a]). This generally leads to a compact set of points to be supported. [START_REF] Eggers | Method and apparatus for automatic support generation for an object made by means of a rapid prototype production method[END_REF] select a subset by downsampling. We follow a similar approach to [START_REF] Chalasani | Support generation for fused deposition modeling[END_REF], considering whether the plastic deposition paths are correctly supported by the layers beneath.

Support geometry.

Once the surfaces requiring support are determined, the support geometry is computed. The main approach consists in extruding the mesh facets requiring support downward, thus defining a support volume. The support volume is usually printed with a weak infill pattern (KISSlicer, Makerware, [START_REF] Strano | A new approach to the design and optimisation of support structures in additive manufacturing[END_REF]). The support is manually removed by breaking it apart from the object. Soluble material can also be used on multiple material printers [START_REF] Kritchman | System and method for printing and supporting three dimensional objects[END_REF]. Printing the support volume uses a significant amount of material and print time, but is very reliable: the support typically has a large area of contact with both the part and the print bed, ensuring the print stability in most cases. The volume is large enough to print without difficulty.

A number of approaches modify the support volume to reduce its size. Huang et al. [2009b] use sloped walls instead of straight walls for the sides, shrinking the support volumes in their middle sections. [START_REF] Heide | Method for generating and building support structures with deposition-based digital manufacturing systems[END_REF] also reduces the support volume by decreasing its size and complexity as the distance below the supported model increases. Several approaches have been proposed to find a model orientation reducing the size of the support volume [START_REF] Frank | Expert system-based selection of the preferred direction of build for rapid prototyping processes[END_REF][START_REF] Allen | Determination and evaluation of support structures in layered manufacturing[END_REF][START_REF] Cheng | Multi-objective optimization of part-building orientation in stereolithography[END_REF][START_REF] Alexander | Part orientation and build cost determination in layered manufacturing[END_REF][START_REF] Majhi | On some geometric optimization problems in layered manufacturing[END_REF]]. We do not consider this issue in our work, and assume that the part orientation has been fixed by the user considering other criteria (stepping error, mechanical robustness, aesthetics of filament orientation).

MeshMixer by Autodesk deviates from the support volume and instead builds a thin structure supporting the part in a sparse, limited number of points. MeshMixer automatically generates an initial support resembling a tree. The precise algorithm is, to our knowledge, undisclosed. This work elegantly shows that a very sparse structure can effectively serve as a support. MeshMixer however often requires the user to fix up the initial structure (see comments on Thingiverse, thing 131054), and the slanted trees sometimes suffer from print reliability issues (see Figure 17). In contrast, our bridges offer similar grouping properties as a tree but print more reliably. [START_REF] Wang | Cost-effective printing of 3d objects with skin-frame structures[END_REF] optimize truss structures for the primary purpose of strengthening 3D printed objects, and extend their approach for support generation. Support beams are added by tracing rays downwards, within a tolerance cone ensuring that the result is printable. The beams are not grouped, missing an opportunity to reduce print time and material usage. [START_REF] Eggers | Method and apparatus for automatic support generation for an object made by means of a rapid prototype production method[END_REF] propose to form a support structure by starting from a regular rhombus mesh filling the print bed. The 3D model is subtracted from the initial structure, removing intersected mesh edges. Points requiring support are attached to the mesh by downward angled beams. A number of heuristics are proposed to reduce the number of beams in the support structure. This approach, however, has to ensure that large enough columns are formed so that the support mesh remains printable. In contrast we optimize for thin elongated bridges that are guaranteed to remain printable. Our approach does not suffer from the orientation bias resulting from canceling edges in a pre-existing mesh.

Adobe Photoshop CC, released on January 16th 2014, includes support generation for 3D printing. Available screenshots reveal that square-section pillars are grown from the ground with a hierarchical tree structure to connect to the surface.

Topology and truss optimization. Truss optimization techniques select and deform the edges of an over-complete initial truss mesh [START_REF] Smith | Creating models of truss structures with optimization[END_REF][START_REF] Wang | Cost-effective printing of 3d objects with skin-frame structures[END_REF]]. While we initially considered a similar formulation, it is difficult to ensure that the result remains printable: the topological optimization is free to remove pillars that are in fact necessary to print the horizontal bridges. This issue also applies to other techniques for topology optimization [START_REF] Allaire | Conception optimale de structures[END_REF] which -preformance concerns apart -cannot easily guarantee that the result can be fabricated.

Stability during printing.

Parts may topple during printing, either due to weight imbalance [START_REF] Chalasani | Support generation for fused deposition modeling[END_REF] or under the friction forces of the printing head. To the best of our knowledge, no approach considers the automatic construction of a support structure ensuring that the printed parts remain stable at all stages of the printing process. Indeed, an object may be balanced once printed, but its -possibly disconnected -subparts may not be stable before all layers are completed. Our approach adds a small set of support points ensuring stability during printing.

A number of other techniques consider geometry and mechanical properties of objects in the context of 3D printing. [START_REF] Stava | Stress relief: improving structural strength of 3d printable objects[END_REF] add struts to reinforce objects but do not consider support generation nor overhang constraints. Prevost et al. [2013] deform and carve objects to obtained balanced objects after fabrication.

Our Method

We discuss in Section 3.1 our choice of using vertical pillars for the main structure, and compare it with trees. Section 3.2 discusses the printing of bridges on FDM printers. Section 4 describes the selection of the points required for supporting the printed model. Our selection ensures both that deposited filament is properly supported, but also that the printed parts remain stable at all times, throughout the printing process. Section 5 introduces our bridge construction algorithm: the generation of the geometry of the support structure once the required support points have been determined. We conclude with results and comparisons in Section 6.

Analysis

An appealing option when designing support structures is to rely on hierarchical tree-like structures. This is a choice worth considering since the support pillars quickly regroup before reaching the printing bed. Therefore, one can expect less material to be used and a smaller print time.

However, this incurs several difficulties. First, printing slanted pillars is generally less reliable than printing vertical pillars. The slope induces a smaller bonding area between layers and an uneven warping during cool down. The reliability varies upon the room temperature, the plastic filament quality, and the layer height settings. Printing vertical pillars is much less sensitive to these factors. Second, even when the structure prints properly, the supported weight and the forces applied by the print head on the upper levels generate torque on the base pillar(s). This bends the structure, and resulting deformations can lead to print failures. In contrast our scaffoldings are stable by construction: the pillars on each side of the bridges prevent the bending of the structure.

One might expect the tree structure to use less material than a bridge structure, thanks to the hierarchical grouping. But as we now discuss, and perhaps somewhat counter-intuitively, bridge structures are in fact comparable to tree-structures. Let us consider a grid of 2 k × 2 k points spaced evenly by one unit (millimeters) on a same horizontal plane. An example is shown Figure 2 for k = 2. The grid side length is 2 k -1 mm. We consider the case of a treestructure with pillars at 45 degrees. Grouping all points down to a single pillar requires a total pillar length of Lt(k) = 2 k (2 k+1 -2).

The tree then has a height of 2 k -1 √ 2 . A bridge structure for the same points at the same height requires a total pillar length of

L b (k) = 2(2 k -1)(1 + √ 2 + 2 k-1
). It can be seen that for k >= 3 the bridge is more efficient than the tree. However, as the height further increases the tree grows a single pillar while the bridge grows four. We consider the height at which a tree-structure and a bridge-structure use the same pillar length as a function of k; that is h such that Lt(k) + h = L b (k) + 4h. For instance, for supporting 16×16 points (k = 4) spaced by 1 mm the tree becomes interesting again after 56 mm. By this time we reach the configuration shown Figure 2 where the tree fails to print properly. In contrast, the four pillars stabilize the bridge structure, making it more reliable to print at higher heights and able to support significant weights.

Bridge Printing Reliability

Our bridges are two layers thick and two threads wide, with a small spacing (0.4 mm) in between both threads. To print bridges at relatively high speeds (60 mm/sec) we force the extrusion of a small amount of plastic prior to printing horizontal bridge segments (0.1 mm of filament). Our bridges are designed to print quickly, which negatively impacts their appearance -in particular, the first printed threads often sag. This has however little impact on the quality of the top of the bridge, as detailed in Figure 3. While all results shown in the paper are printed on a Makerbot Replicator 1 with ABS plastic, we also tested our bridges successfully on an Ultimaker 2 with PLA plastic, using same parameters. Our scaffolding algorithm is independent from the exact geometry used to print bridges.

The bridges are mechanically robust despite their small size (see Section 1). Two 30 mm bridges can for instance support the entire Minotaur model of Figure 17 with little deflection (< 0.3 mm).

Support Points

The first step of our approach is to determine a set of points that require support. There are two aspects to this process: supporting filament and ensuring part stability. We start by determining where filament needs support: these points are required regardless of stability, whereas the stability analysis of the overall part depends upon the already placed support points.

Supporting Filament

Our approach starts by slicing the model without any support, determining the full set of print paths. Each print path is a sequence of segments along which plastic has to be deposited. The print paths are of two types: the perimeters which follow the outer boundary of the surface and the infills which fill the interior of the volume.

Our algorithm walks along each print path and checks whether each segment endpoint is properly supported by the layer just below. The test considers the coverage of a disk having for diameter the size of the print nozzle (0.4mm in our setup). If more than 50% of the disk lies outside the object on the layer below, we consider the endpoint unsupported -this threshold was determined experimentally to ensure good surface quality. In practice, we implement the test using images of the layers with 0.05mm pixel resolution. We only check segment end points since the segments themselves form bridges if their extremities are supported. However, in order to ensure a good quality for bottom surfaces, we restrict the longest segment length. This simple analysis does not take into account the fact that when a point is supported, a whole length of filament around it can be considered supported as well -the cooling filament having a non negligible rigidity. This is the case on perimeters. This effect turns into a surface support when filaments are deposited side by side, for instance when filling an area with a tight infill pattern (see [START_REF] Chalasani | Support generation for fused deposition modeling[END_REF] for a nomenclature of such cases). We therefore select only a subset of the detected points. Pseudo code is given by Algorithm 1. C(u, v) denotes the curvilinear distance between two points u and v on a same print path; τ is the canceling distance (2mm in our implementation); isUnsupported tests disk coverage test using the layer directly below the point. Figure 4 shows the result for a box hanging in empty space.

Ensuring Part Stability

Once the points required for supporting filament are determined, we consider the stability of the printed part. When printed layer by layer an object made of a single component often starts as disconnected subparts which regroup at higher heights (see Figure 5). At an intermediate stage, each of the disconnected sub-parts may be subject to instabilities and topple, leading to a print failure. Our analysis algorithm therefore proceeds in a bottom-up manner, analyzing layer after layer the stability of each subpart independently until they regroup.

We assume next that there is no gluing force between the bed and the printed object -a conservative assumption since any existing gluing force only improves stability. We also assume that the part is rigid when checking for equilibrium and stability.

Stability conditions. Verifying whether a rigid body lying on a surface is under static equilibrium involves two main concepts: the center of mass (CoM) of the object as well as its base of support (BoS). For an object of volume Ω of homogeneous density ρ the center of mass is defined as Com(Ω) = ρ Ω xdx. In the case of FDM printed object, the volume Ω to consider is not the volume defined by the mesh, but instead the volume resulting from the accumulation of plastic filament -this is especially important when sparse infill patterns are used within the object interior. The BoS is the convex hull of the points of the printed part in contact with the print bed. Our goal is to increase the BoS to ensure stability, through the addition of support points and bridges.

A rigid body lies in static equilibrium on a plane orthogonal to gravity if its CoM projects into the BoS (e.g. [START_REF] Prévost | Make It Stand: Balancing shapes for 3D fabrication[END_REF]). This equilibrium might however be unstable if small perturbations -for instance due to the print head -make the object topple. We take these perturbations into account by verifying whether a disk of radius r around the projected CoM lies entirely within the base of support. This is an approximation, and we choose for radius a conservative estimate of 3mm in our implementation. A more elaborate scheme would change the radius depending of the distribution of mass around the CoM and the distance to the BoS; we did not find this necessary.

When a subpart is detected as unstable we add support points to increase its base of support. This is only possible because the base of support of our scaffoldings always contains all the projected support points: the bridges are always supported by vertical pillars at their extremities.

Algorithm. Our algorithm sweeps through layers from bottom to top. At each layer, we render an image of the print paths (one pixel per 0.05 mm) and use it to keep track of the 3D connected components. Note that this only requires the images of the current layer and the layer directly below. An example of layer image is shown in Figure 6, right.

We compute the CoM of each component by summing the coordinates of the pixels belonging to it -each pixel represents a small volume of matter having a same unit mass. Using the image of the print paths properly accounts for infill patterns within the object.

While sweeping through layers we keep track of the current BoS of each 3D component (Figure 6, right, green polygons). A BoS is a convex hull and therefore its geometric complexity remains small. Each BoS is initialized at the first layer, where the filament is in direct contact with the print bed: we add all the pixel coordinates belonging to a component to its BoS. At each layer, we include in the BoS the support points detected for the filament. We then check whether the disk of radius r centered on the projected CoM is entirely within the BoS (Figure 6, right, orange circles). If that is the case for all components we continue to the next layer. If the CoM disk leaves its BoS new support points have to be added. During the sweep we keep track of candidate points for each component: these are points on the bottom surface of the object that are not projecting in the component BoS. By supporting these points we have an opportunity to enlarge the BoS of the component. We do not consider the candidate point directly but a circle of points around it. The radius is the same as for the CoM disk. This guarantees that we can always enlarge a BoS to cover the CoM disk.

To enlarge a BoS we iteratively add points until the CoM disk is fully covered. At each iteration we add the candidate enlarging the BoS with the largest coverage of the CoM disk. Due to the arbitrary insertion order, some points added in the first iterations may no longer contribute to the final BoS. We remove these and tag the selected points as requiring support. The added points may not be in contact with the surface, in which case we add a small bridge between the candidate point and the surface point (Figure 6, right, purple segments). This bridge is given as an input to the scaffolding algorithm.

Figure 6, left illustrates the bridge structure resulting from the stability analysis only. Note in particular how the BoS has been enlarged by adding bridges at the first layer, providing an automated raft feature for small contact surfaces with the bed. Timings for this algorithm are summarized in Table 1.

Scaffolding

We now describe how the geometry of our support structure is generated, given the set of points to be supported. We seek to generate a structure so that:

-the structure is formed by vertical pillars and horizontal bridges, -all required points are properly supported by vertical pillars, -the vertical pillars connect either to the print bed, to horizontal bridges located below, or to the object itself. -all horizontal bridges are supported at their extremities, by vertical pillars, by other bridges, or by connecting to the object. This last point guarantees that the structure is printable on an FDM printer. We search for a structure using a small amount of plastic while enforcing these constraints.

Our initial attempts at formulating an integer problem in a regular grid, capturing the constraints between horizontal bridges and vertical pillars resulted in impractical computation times -it did not terminate but for the simplest examples. This formulation is described in the supplemental material. We therefore propose a greedy optimization algorithm.

We design our algorithm with the ability to create bridges in several directions in the XY plane. This is important since a strong direc-tional bias -such as axis aligned bridges only -would generate a larger number of pillars when supporting features at an angle. We also note that while thin slanted pillars become less reliable as their length increases, they can print reliably on short distances. This is particularly useful when trying to support several points with a rectilinear bridge: perfect alignments are unlikely. Our algorithm therefore has the ability to connect vertical pillars to other elements by adding a small slanted connector at their top.

Bridge Gain and Score

Our algorithm enumerates and selects new bridges that improve the current solution. It therefore requires a function to estimate the benefit of a new bridge. We approximate the bridge benefit by counting the gain and loss in terms of pillar and bridge length. When deciding which bridge to insert we compute a score for each bridge. The score is:

Score(b) = Gain(b) -k • lmax(b)
, where lmax(b) is computed as the maximum length of the structure connecting an element above to the bridge. It takes into account non vertical parts that may occur when an element above is not in the vertical plane of the bridge. The score penalizes uneven distributions of connection lengths above the bridge. The bridge giving the best (possibly negative) score will be selected.

In cases where the bridge extremities are above the object, we use the free length of each vertical pillar instead of the bridge height:

Gain(b) = k • h b -h1 -h2 -w b
with h1 and h2 the heights of the pillars before reaching the object. lmin (see the inset) is a parameter fixing the minimal distance between a bridge and a supported point (1.6 mm in our implementation). Note that lowering the bridge would only reduce its gain. Thus bridges have maximal gain at a distance lmin below the lower of the elements they support. This provides a way to efficiently enumerate possible bridge heights.

Construction Algorithm

The input to our bridging algorithm is a set of points and bridges that have to be supported. The bridges come from the stability analysis (Section 4.2). We also input a representation of the 3D model allowing for fast line intersection tests -this can be any of the common ray-tracing data-structures.

The output of the algorithm is a set of horizontal bridges and vertical pillars forming a correct (printable) bridge structure while having a small size. Each computed bridge and pillar is turned into actually geometry before 3D printing (Section 5.3).

Sweep strategy. Our algorithm iteratively searches for possible bridges throughout the volume, adding those with the highest score. Since the set of points requiring support is sparse only a small number of possible bridges has to be considered.

Our approach is based on a sweep strategy. Possible bridges are enumerated by sweeping a vertical plane along a fixed direction in the XY-plane. For the sake of clarity let us assume in the following that the selected sweep direction is the X axis. We thus sweep a YZ plane along the X axis, stopping at a number of events. The events represent opportunities to create bridges orthogonal to the sweep X Y sweep bridges?

Figure 7: Two bridges and an isolated point as well as their corresponding anchoring segments for a sweep along the X axis. The green squares are events considered during the sweep. The purple line illustrates the YZ sweep plane when examining one event.

Bridges will be searched along the Y and Z axis. All intersected anchoring segments are an opportunity for a new bridge to support existing bridges and points.

direction that support other bridges and points located above. The events are the end points and intersections of a number of anchoring segments describing where bridges and points can be supported.

Anchoring segments for bridges. A bridge is represented by a solid segment supporting elements above. Two anchoring segments -one on each extremity -represent where the bridge can be supported from below: the interval of possible endpoints for this bridge. The anchoring segments for a bridge are outlined in green in Figure 7. Their length is chosen to enforce a longest bridge constraint (30 mm in our implementation).

Supporting pillars from below can connect anywhere along the anchoring segments. Once connected, the bridge extends to the pillar and the anchoring segment is removed. The remaining anchoring segment, if any, is updated to enforce the longest bridge constraint. We name this operation a snap, and name open bridge a bridge with two open anchoring segments and a half-open bridge a bridge with a single open anchoring segment. The exact size of the bridge is only determined once both of its anchoring segments are snapped.

X Z

Anchoring segments for points. Points are supported by pillars grown either from the ground or from a bridge located below. Using only vertical pillars would require a perfect alignment between bridges and points, an unlikely event. Instead, our algorithm allows small slanted bars to be used at the top of vertical pillars, as illustrated in the inset. To ensure printability we constrain the ratio between the offset at the top and the height of the slanted bar. The two dashed lines in the inset show extremal configurations, with the point either exactly above the pillar or at the largest admissible offset (5 mm in our implementation).

Anchoring segments for a point depend on the sweep direction. They are illustrated in orange in Figure 7. The anchoring segments for points are created each time a new sweep direction is selected. Note that we consider the extremities of the solid segment of a bridge as points to be supported (Figure 7). If one extremity is snapped, the corresponding bridge anchoring segment is removed.

Complete algorithm. The full pseudo-code is given in Algorithm 2. At every iteration (line 2) the algorithm starts with a number of (half-)open bridges and points and attempts to snap as many as possible by adding a new bridge supporting them from below through pillars. When the algorithm cannot find beneficial bridges (G(b) > 0) it stops (line 15). the sweep direction with the X axis. Possible bridges are enumerated by sweeping the YZ plane along the X axis, stopping at each event (lines 7-8). The events are the end points and intersections of all anchoring segments -the intersection being computed after projection on the XY plane, i.e. ignoring the Z coordinate. Figure 7 illustrates the set of events for a simple case. createAnchoringSegments creates all anchoring segments for bridges and points (see Figure 7); events computes all events for the sweep (green squares in Figure 7). At each event, we consider the bridges that can be formed along the Y axis, connecting the segments currently intersected by the sweep plane. Bridges can exist at different heights: we consider the heights just below each of the anchoring segments (see Section 5.1). This is performed by selectBridge (line 11), described in Algorithm 3.

The algorithm considers multiple sweep directions at each iteration (line 4). Let us assume that the problem is rotated each time to align

In Algorithm 3, each bridge snapping more than two points is evaluated by the functions addSupported and evalBridge which implement the bridge gain and score evaluation described in Section 5.1. The gain and score are computed assuming that the current endpoints are supported by straight pillars -which is an approximation of the final solution. The score takes into account the increase in length of the bridges located above that are snapped to the new bridge (see lmax in Section 5.1). Candidate bridges are tested for collisions by collisions: this checks whether a collision occurs between the model, the bridge and each connector to the elements above it. This takes into account collisions with already placed bridges. The collision tests can be accelerated thanks to the fixed number of directions and the limited set of points to consider.

Finally, snap (line 18, Algorithm 2) snaps the extremity c of an element located above to the newly added bridge B by creating a vertical pillar topped (if necessary) by a small slanted pillar. For instance, that would be the case where the purple line in Figure 7 intersects orange segments: a slanted bar is necessary to cover the horizontal gap from the point to the bridge. Note that the distance between the point and the intersection along the anchoring segments constrains the height of the bridge. This is taken into account by z(c) in Algorithm 3, together with the minimum distance between a bridge and an element, lmin. Table 1: Executions times on a variety of models.

for i2 ← i1 to size(C) -1 do 7 if C[i2] -C[i1] maxDist then 8 addSupported(A, C[i2]); 9 if collisions(A,
Note that in some cases the new bridge might be able to support two anchoring segments of a same bridge located above ; i.e. a bridge anchoring segment and a point anchoring segment. This case can be seen for the rightmost segment and the purple sweep line in Figure 7. If there is more than one possibility to snap an element to the current bridge, only the one yielding the connector of smallest length is considered.

Complexity Algorithm 2 has a total time complexity of

O(d • (n + k)n 3 • c • b)
, where d is the number of sweeping directions, n the number of points to support, k the number of intersections between the segments projected on the XY plane, c the maximum time complexity of a collision test, and b the number of newly added bridges during the main loop of Algorithm 2. Note that this is only an upper bound, and that in practice the execution time of the whole process is reasonable (see Table 1). Several factors are favorable. First, the iterations for different sweep directions are trivial to parallelize. Second, the number of segments input to selectBridge can be much smaller than the total number of element n (not all anchoring segments intersect). Finally, for each new bridge that is added all the points it supports are removed, making subsequent iterations within Algorithm 2 faster.

We measured the execution time of our parallel implementation on an Intel R Core TM i7-4770K @ 3.50GHz with 8 threads, 32 GB RAM and a GeForce GTX Titan. We used d = 8 sweeping directions (angular increments of π 8 due to symmetry). As we can see in Table 1, the timing for most real-world examples are under five minutes and we believe there is room for further optimizations.

Connecting to the object. The extremities of a bridge may connect to the top of the surface below by a vertical pillar. As an alternative, we also consider snapping bridges to the object sides, as illustrated in the inset. For each bridge considered in line 10 of Algorithm 3, we also consider extended the same bridge with endpoints until touching the surface (up to the maximum allowable length). Such a candidate bridge simply has one of its h {1,2} equals to 0 in the calculation of its score and gain (Section 5.1). We retain the candidate bridge with the best score.

Producing the Final Geometry

The final geometry is an union of box and cylinder primitives. We rely on cross-section pillars that we found more reliable to print than cylinders. Bridges are formed of two parallel one-thread thick segments, across two layers. Figure 8 reveals the main components of our bridge structures. Our slicer processes union of meshes without suffering from inter-penetration issues.

We adapt our slicer [?] for printing the scaffoldings. In each slice we erode by 0.2mm the bridge structure where it comes in contact with the object. This helps the removal of parts of the structure connecting to the object. For sideway connections to the object (Figure 8, second closeup form the left) we add a one-layer thick protrusion from the object, providing a docking space for the bridge. This tiny loop of plastic easily breaks away.

Results and Discussion

We compare the behavior of different methods running in automatic mode: we perform no manual editing of the proposed support structures. Our technique runs with the exact same settings for all models. All models are printed on a Makerbot Replicator 1 Dual using ABS plastic at 40 mm/sec print speed for perimeters, 60 mm print speed for other print paths (including support) and 120 mm/sec travel speed, using layers of 0.2 mm height. The only exception is Table 2 where we match the settings of Makerware.

Figure 11 compares MeshMixer and our technique on the Enterprise 3D model. We generate a support in MeshMixer and load it into our slicer to compute the used filament length. We adjusted two parameters in MeshMixer: the angle threshold (40) and density (80) to match as closely as possible our support density. MeshMixer uses 9.7m of filament while our technique uses 9.89m -similar amounts. However, our approach ensures a more uniform support. This is visible under the propulsion units, but also under the main body. On this model, the support from Makeware (not shown) uses 18.8m of filament as it fills the space below the model. We show a comparison to Photoshop CC in Figure 12. With our technique long bridges supported by few pillars replace dense trees. Using parameters from PhotoshopCC (Replicator 1 profile), PhotoshopCC uses 4.61m of filament in the support (11.97m total) versus 2.31m for our technique (9.48m total). Our printed version is shown Figure 9. Table 2 summarizes other comparisons. In this table we use Makerware as the slicer for the MeshMixer output. We use 40 mm/sec for printing and 80 mm/sec for travel. We match the settings of Makerware in our slicer. Makerware and MeshMixer explicitly avoid supporting the bridge overhangs in Servojoint. Our technique gives a rougher surface but the bond between layers is improved. Despite the increase in required support points our structure remains three times smaller than the one of Makerware. Knot is a defavorable case for our technique. Makerware and MeshMixer support very few points through thin beams while our approach builds a full bridge. For this object, with both the Makerware and MeshMixer models we had to use a raft for the part to remain stable on the heated bed. In all other cases we use significantly less plastic than Makerware. Our print times are comparable to Makerware, which is in large part due to the printing of the many small connectors. We believe print times could be significantly reduced by grouping connectors supported by a same bridge into continuous connectors.

Additional Results

Figure 15 is a tall and intricate design mimicking the helix of DNA. Figure 16 shows three additional models with very different geometries. Note the elegant scaffolding generated for the Gymnast model. The Hilbert cube is a case where bridges have little room to exist -the scaffolding is nevertheless successfully created. Our version of the 5cm bunny peel model uses 1.97g of plastic versus only 0.75g for the MeshMixer version, which has been manually optimized (see http://www.thingiverse. com/thing:131054/#comments, user meshmixer). Figure 1 is printed with PLA plastic on an Ultimaker 2 with 0.3 mm layer height, all other parameters being the same.

Support Removal

Support detaches from the object when applying gentle force and we clean most objects by hand, sometimes using a small wire cutter on interleaved bridges in complex geometries. The support leaves faint white marks on the plastic -a default shared by all techniques. These can removed by heating the plastic or by finishing the part in acetone vapor. We did not apply such techniques to the results shown here. Soluble material could be used to print our structures.

Limitations

Our method does not consider the robustness of the printed object.

It can be frustrating to discover that a perfect print with support is in fact too fragile -a difficulty worsened by the support removal step. The Enterprise model in Figure 9 is such a case: the thin connectors between the engines and the body (<1.5mm) broke during cleanup where they connect to the engines. We had to glue them back (no other model required gluing). Automatic methods exist for the purpose of reinforcing objects [START_REF] Stava | Stress relief: improving structural strength of 3d printable objects[END_REF].

Our sweeping algorithm is unaware of the geometry of the object aside from the collision detection. For instance, it might miss an opportunity to create a bridge where there is a hole through the object. Analyzing the shape to guide the algorithm is an interesting avenue of future work. This is simple to integrate in our algorithm which already takes open bridges as input.

As explained Section 3.2 when printing a bridge the first thread fails in approximatively 12 % of cases, leaving hanging filament in the print. This is visible in figures showing the print before cleanup. This has little impact on surface quality as falling filament cools quickly and does not bond with the surface below.

Conclusion

We have shown how to exploit a specific property of FFF printers -their ability to print bridges across gaps -to construct reliable scaffoldings. Their geometry gives to our scaffolding interesting mechanical properties that makes them sturdier and more stable, even at the smallest thickness ensuring that they print correctly. Our structures could probably benefit other processes such as stereolithography -but the set of requirements are different.

Further reducing the quantity of material usage while preserving reliability will require a precise modeling of the mechanical properties of the structure and object throughout the print process. This is a challenging task since the plastic deposited in layers has an anisotropic behavior which we expect to become highly nonlinear on thin slanted structures. This is nevertheless an exciting venue of future work. In the meantime our technique provides a simple and reliable way to print interesting and complex geometries with a reasonnable material usage.

Figure 2 :

 2 Figure 2: Left, top: A bridge structure supporting a grid of 4 × 4 points. Left, bottom: Corresponding tree structure. Pictures, from left to right: A bridge structure 78mm tall, the same structure supporting a 9 volt battery, the equivalent tree (same amount of filament). The tree cannot support such weight without toppling. In addition, the top of the tree failed to properly print due to extruder friction. Printed at 60mm/sec on a Replicator 1 Dual with ABS plastic.

Figure 3 :

 3 Figure3: We printed bridges of 30 mm length in batches, along the X, Y axis and at a 45 degree angle. All the bridges printed successfully with a flat top surface. However, the first threads of plastic often sag, resulting in an uneven underside. We measure the deflection to be 0.8 mm on average. In 12% of the cases a first thread failed to connect and was dangling from the bridge. Printed at 60mm/sec on a Replicator 1 Dual with ABS plastic extruded at 220 • C.

Figure 4 :

 4 Figure 4: Cube hanging in space. Left: Set of points requiring support. Middle: Generated scaffold. Right: Bottom surface quality.

Figure 5 :

 5 Figure 5: Left: A stable object. Right: At an earlier stage of printing the object is made of four disconnected components. The center of mass (red dot) of the full object (left) projects onto the ground (green dot) within the base of support (orange polygon). At an earlier stage of printing (right) the object is made of four disconnected components which are unstable and may topple if unsupported. As can be seen the projected CoM lies outside of the BoS.

Figure 6 :

 6 Figure 6: Left: Bridge structure stabilizing the part: the projected CoMs are now within the BoSs. Right: Image of a layer created during stability analysis. The print paths are color-coded with the ID of their 3D connected component. The orange circle are the CoM disks, the green polygons the current BoS of each component. The purple segments are the added stabilizing bridges at this stage. They maintain the orange CoM circle within the green BoS polygon.

  the inset, a bridge of length w b at height h b supporting k elements provides a gain of Gain(b) = (k -2)h b -w b . Clearly, only bridges supporting more than two points can be beneficial. Our algorithm only inserts bridges where Gain(b) > 0.

Algorithm 2 :

 2 Generate scaffolding Input: A set of required points R ∈ R 3 , a set of required bridges B, the number of sweep directions d Output: A valid bridge structure 1 Initialize the active set of elements with E ← R ∪ B; ; // set of segments crossing the current sweeping plane 7 Q ← events(S) ; // queue sorted by X 8 while Q = ∅ do 9 e ← pop(Q) ; // leftmost event 10 for s ∈ S starting in e do P ← P ∪ s ; 11 selected ← selectBridge(P ); 12 if score(selected) > score(bestBridge) then 13 bestBridge ← selected 14 for s ∈ S ending in e do P ← P \ s ; 15 if bestBridge = ∅ then return; 16 Let C bet the set of elements supported by bestBridge; 17 for c ∈ C do 18 snap(c, bestBridge); 19 E ← E ∪ B;

Algorithm 3 :

 3 Select a bridge along a given plane Input: Set of segments P intersecting the sweep plane YZ at current event 1 C ← {P ∩ Y Z} ; // intersections sorted by Y 2 Z ← {z(c), c ∈ C} ; // sorted by Z 3 for z ∈ Z do 4 for i1 ← 0 to size(C) -1 do 5 A ← ∅ ; // points supported by bridge

  6

Figure 8 :

 8 Figure 8: From left to right: The gymnast model and its scaffolding. A pillar, a sideway connector, vertical connectors supporting filament, the mid-air support for the right foot. Model: http://www.123dapp.com/123C-3D-Model/Female-Gymnastics-Cartwheel/711240

Figure 9 :

 9 Figure 9: Top: Printout of the Enterprise model. Bottom: Underside after cleanup. We broke the engine connectors during cleanup and had to glue them back (only case where glue was involved). Print time: 3h14, 9.89m of filament.

Figure 10 :

 10 Figure 10: Comparison between MeshMixer (left) and our technique (right). MeshMixer uses 6.7m of filament versus 7.66m for our technique. The tree generated by MeshMixer is fragile: a single pillar supports the entire weight of the arms through long slanted bars. Model: http://www.thingiverse.com/thing:46646 by user ajolivette

Figure 11 :

 11 Figure 11: Comparison between MeshMixer (top) and our technique (bottom). The middle row shows underside views. MeshMixer uses 9.7m of filament while we use 9.89m. Notice the much denser support we provide in particular to the rear of the ship.

Figure 12 :

 12 Figure 12: Comparison between Photoshop CC (left) and our technique (right). Model: thingiverse.com/thing:18346 by user JackSpectre.

Figure 13 :

 13 Figure 13: Servojoint. Makerware, MeshMixer, Ours.

Figure 14 :Table 2 :

 142 Figure 14: Knot. Makerware, MeshMixer, Ours. Model: thingiverse.com/thing:5506 by chylld

Figure 15 :

 15 Figure 15: Left: Scaffolding for the DNA model. Middle: After printing. Right: After cleanup. Print time: 3h36, 8.7m of filament.

Figure 16 :

 16 Figure 16: Models printed with our technique, scaffoldings on the left and cleanup model on the right. Top: The Gymnast model. Middle: The curved Hilbert cube model. Bottom: The 5cm Bunny Peel model. Hilbert cube model: thingiverse.com/thing:16343 by tbuser. Bunny peel model: thingiverse.com/thing:131054 by user meshmixer.

Figure 17 :

 17 Figure 17: Top left: The Minotaur printed with our technique. Print time: 2h37m, 7.66m of filament. Top right: Attempt at printing the MeshMixer version. Print time (same parameters): 2h04, 6.7m of plastic. We also had to add a raft below each feet. On our model, the stability analysis automatically added a raft beneath each feet (visible in picture). Bottom: Model printed with our technique after clean up, front and back.

Acknowledgements

This work was funded by ERC grant ShapeForge (StG-2012-307877). We thank the anonymous reviewers for their help with improving the paper, our families for accepting the 3D printers at home for long print sessions, as well as the 3D printing community members who shared the models shown here.