IRIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<table><tr><td>ARCHIVES</td></tr></table>

MANIPULATION DE SURFACE
EN CONCEPTION
ASSISTÉE PAR ORDINATEUR

<figure><img src="image_1.png" /></figure>

Michel GRAVE

Rapport de Recherche N° 210

Décembre 1976
MANIPULATION DE SURFACES EN
CONCEPTION ASSISTÉE PAR ORDINATEUR

Michel GRAVE

IRIA - LABORIA

RÉSUMÉ

Le but de ce rapport est de présenter, d'une part les principales techniques utilisées actuellement pour la manipulation des surfaces dans les applications en C.A.O. et d'autre part quelques-uns des problèmes liés à la réalisation d'un programme interactif en utilisant le système GIPSY [9]. Cette deuxième partie sera surtout axée sur les problèmes d'interaction, les problèmes mathématiques posés par la représentation de surfaces choisie n'étant que brièvement présentés.

ABSTRACT

The purpose of this report, is to present first the main techniques used for the manipulation of surfaces in C.A.O., secondly some of the problems encountered in the implementation of an interactive program using GIPSY [9].

In this second part, we shall emphasize the interaction problems ; the mathematical problems coming from the choosen representation of surfaces are only presented briefly.

<footnote>* IRIA - LABORIA - 78150 Le Chesnay (France)</footnote>

<footnote>** Département de Mathématiques, Université Paris-Nord, Av. J.B. Clément - 93 Villetaneuse (France)</footnote>
# SOMMAIRE

<table><tr><td>Table des figures</td><td>2</td></tr><tr><td>Introduction</td><td>3</td></tr><tr><td>1. Notations</td><td>4</td></tr><tr><td>2. Méthode de BEZIER</td><td>5</td></tr><tr><td>2.1. Courbes UNISURF</td><td>5</td></tr><tr><td>2.2. Surfaces UNISURF</td><td>9</td></tr><tr><td>3. Méthode de RIESENFELD</td><td>12</td></tr><tr><td>3.1. Etude des B-splines</td><td>12</td></tr><tr><td>3.2. Courbes RB<sup>3</sup></td><td>14</td></tr><tr><td>4. Méthode de COONS</td><td></td></tr><tr><td>4.1. Principe de la méthode</td><td>19</td></tr><tr><td>4.2. Raccordement des carreaux</td><td>19</td></tr><tr><td>4.3. Surface de correction</td><td>21</td></tr><tr><td>4.4. Forme polynomiale</td><td>22</td></tr><tr><td>5. Manipulation de volumes</td><td>25</td></tr><tr><td>5.1. Opérations sur les volumes</td><td></td></tr><tr><td>5.2. Définition des enveloppes des objets</td><td>26</td></tr><tr><td>6. Réalisation d'un programme interactif</td><td>30</td></tr><tr><td>6.1. Principes généraux</td><td>30</td></tr><tr><td>6.2. Correspondance COONS-BEZIER</td><td>31</td></tr><tr><td>6.2.1. Expression matricielle de l'équation de BEZIER</td><td>31</td></tr><tr><td>6.2.2. Formules de changement de matrices</td><td>31</td></tr><tr><td>6.3. Interactions</td><td>32</td></tr><tr><td>6.3.1. Comparaison des deux méthodes</td><td>32</td></tr><tr><td>6.3.2. Interactions en trois dimensions</td><td>34</td></tr></table>

## Annexe

A1 Présentation de quelques techniques utilisées pour fixer les valeurs des dérivées croisées dans la méthode de CONS

## Références
Table des figures

<table><tbody><tr><td>Fig.1.</td><td>Exemples de courbes Unisurf avec les polygones</td><td>6</td></tr><tr><td>Fig.2.</td><td>Famille de fonctions (m)u<sup>i</sup>(1-u)<sup>m-i</sup> pour m = 5</td><td>8</td></tr><tr><td>Fig.3.</td><td>Exemples de surfaces Unisurf avec les polyhèdres</td><td>10</td></tr><tr><td>Fig.4.</td><td>Influence des points du polyhèdre sur la forme de la courbe</td><td>11</td></tr><tr><td>Fig.5.</td><td>B-Splines (N<sub>o,m</sub>(x) avec x<sub>i</sub> = i)</td><td>13</td></tr><tr><td>Fig.6.</td><td>B-Splines ayant des noeuds confondus</td><td>15</td></tr><tr><td>Fig.7.</td><td>Courbes Unisurf et RB<sup>3</sup> correspondant aux mêmes polygones (ouverts)</td><td>16</td></tr><tr><td>Fig.8.</td><td>Courbes Unisurf et RB<sup>3</sup> correspondant aux mêmes polygones (fermés)</td><td>17</td></tr><tr><td>Fig.9.</td><td>Fonctions F<sub>i</sub> et G<sub>i</sub> choisies parmi les polynomes de degré 3</td><td>23</td></tr><tr><td>Fig.10.</td><td>Diagramme d'états du programme</td><td>29</td></tr><tr><td>Fig.11.</td><td>Effet de la modification d'un point sur un rectangle quand on utilise la méthode de COONS</td><td>33</td></tr><tr><td>Fig.12.</td><td>Exemple d'interaction</td><td>35</td></tr></tbody></table>
## Introduction

Le développement des machines outils à commande numérique et des systèmes graphiques interactifs à amené de nombreuses personnes à travailler sur le problème de la représentation et de la manipulation des formes.
Les surfaces, en particulier ont fait l'objet de nombreuses études.

Les méthodes mises au point ces dernières années ont donné lieu à de nombreuses applications. Des firmes telles que RENAULT, BOEING, DASSAULT ont ainsi réussi à réduire de façon très importante (rapport de l'ordre de 1 à 100 chez RENAULT) le temps nécessaire à la réalisation des maquettes de voitures ou d'avions.

Ce rapport présentera les principales méthodes utilisées actuellement pour concevoir les surfaces :

- méthode de Bézier (Régie Renault)

- méthode de Riesenfeld (Université d'UTAH)

- méthode de Coons (Massachusetts Institute of Technology)

En ce qui concerne les surfaces, Forrest (cité par Riesenfeld [16]) a défini le problème de la façon suivante :

> Il faut non seulement représenter les formes voulues de façon fidèle et sous un aspect qui se prête au calcul, mais il faut également fournir un bon interface entre un utilisateur, qui n'est pas nécessairement un mathématicien, et la représentation mathématique des formes qu'il manipule.

Dans ce rapport, il sera surtout question du second point : l'interface entre l'utilisateur et les équations de surfaces, les trois méthodes présentées utilisant toutes la représentation par équations paramétriques. Les fonctions $f(u,v)$ (u et v étant les paramètres) seront soit des polynomes, soit des fonctions splines constituées de polynomes. Le premier point sera cependant abordé lors de la présentation de la méthode de Riesenfeld qui, tout en conservant la même interface que celui utilisé dans la méthode de Bézier, a remplacé les polynomes par des fonctions splines.
Dans le paragraphe 5, le problème de la manipulation de volumes représentés par des enveloppes définies par les méthodes citées dans les paragraphes précédents sera brièvement présenté.

Dans le paragraphe 6, enfin, il sera présenté quelques uns des problèmes posés par la réalisation d'un programme interactif de manipulation de surfaces.

# 1. Notations

Lorsque l'on désire définir une surface, il est en général difficile de le faire à l'aide d'une seule équation. On est donc souvent amené à découper la surface en plus petits éléments qui, dans ce qui suit, seront appelés carreaux.

Dans les chapitres qui suivent, on notera $f(u)$ ou $f(u,v)$ des fonctions vectorielles (sauf spécification contraire) qui seront des fonctions paramétriques dont les paramètres varieront entre 0 et 1.

En réalité, quand on rencontrera une formule du type

$f(u,v) = g(u,v)$ il faudra considérer que l'on a n équations simul-tanées, si l'on travaille dans un espace à n dimension :

$$ 
\begin{aligned}
f_1(u,v) &= g_1(u,v) \\
\vdots \\
f_n(u,v) &= g_n(u,v)
\end{aligned}
 $$

En general, ce sera 4 ou 3 dimensions selon que l'on utilise ou non les coordonnées homogènes (voir à ce sujet COONS et HERZOG dans [17]).
## 2. Méthode de BEZIER

Cette méthode, connue aussi sous le nom de "procédé UNISURF", a été mise au point par le Professeur BEZIER, à la Régie Renault pour être utilisée par les personnes ayant à concevoir les carosseries des automobiles. Dans ce cas, les critères de jugement des surfaces sont beaucoup plus d'ordre esthétique que mathématique (aérodynamique ou autres). De plus, les utilisateurs n'étant pas des mathématiciens, ils ne doivent pas avoir à se préoccuper de la représentation interne. Le principe de la méthode sera tout à abord présenté pour les courbes, la généralisation aux surfaces se faisant ensuite aisément.

### 2.1. Courbes Unisurf

Une portion de courbe est définie à l'aide d'une ligne brisée, qui sera appelée polygone dans ce qui suit, dont les sommets serviront au calcul de l'équation de la courbe, et qui représentera grossièrement l'allure de la courbe. (voir exemples sur la figure 1).

L'équation de la portion de courbe est obtenue à l'aide d'une formule d'approximation du type

$$ f(u) = \sum_{i=0}^{n} f^*\left(\frac{i}{n}\right) \cdot J_{n,i}(u) \quad (1) $$

où $f^*(\frac{i}{n})$ ($0 \le i \le n$) denote (1) le vecteur associé au sommet i du polygone et $J_{n,i}(u)$ est une fonction scalaire. Ces fonctions sont définies de telle façon que l'arc de courbe présente les propriétés suivantes :

i - Les extrémités de l'arc sont les extrémités du polygone :

$$ f(0) = f^*(\frac{0}{n}) \quad \text{et} \quad f(1) = f^*(\frac{n}{n}) $$

ii - L'arc de courbe, au point $u = 0$, est tangent au vecteur défini par

$$ f^*(\frac{0}{n}) \quad \text{et} \quad f^*(\frac{1}{n}), \text{ et au point } u = 1, \text{ il est tangent au vecteur défini par } f^*(\frac{n-1}{n}) \text{ et } f^*(\frac{n}{n}) $$

<footnote>(1) la notation sera justifiée dans l'étude des fonctions de Bernstein.</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1. Exemples de courbes Unisurf avec les polygones</figcaption></figure>
iii - de façon plus générale, la dérivée d'ordre p au point u = 0
dépendra des p + 1 points $f^*(\frac{o}{n})$, ..., $f^*(\frac{p}{n})$, et au point
u = 1, elle dépendra de $f^*(\frac{n-p}{n})$, ..., $f^*(\frac{n}{n})$

Plusieurs familles de fonctions J<sub>n,i</sub> vérifient ces propriétés, les fonctions
retenues ont été les polynomes de Bernstein, sôit :

$$
J_{n,i}(t) = \binom{n}{i} t^i (1-t)^{n-i} \quad (2)
$$

Une étude détaillée de cette famille de polynomes a été faite par
Riesenfeld [16]. Nous ne retiendrons ici que quelques unes des propriétés :

i - Le maximum de la fonction J<sub>n,i</sub>(t) se trouve en

$t = \frac{i}{n}$

ce qui signifie que le point noté $f^*(\frac{i}{n})$ du polygone aura son
influence maximale sur le point $t = \frac{n}{n}$ de la courbe (ce qui
explique la notation choisie)

ii- en t = i/n J_{n,i}(t) vaut approximativement 1/3 : une modification
δf du point f*(i/n) entrainera donc une variation δf/3 de la
valeur f(i/n)
(ces deux propriétés ne sont valables que pour i / {0,n})

iii- $J_{n,i}(t)$ est non nulle sur l'intervalle $]0,1[$ : une modification de l'un des points du polygone aura des répercussions sur toute la courbe.

La figure 2 montre la famille de fonctions $J_5,i(u)$

La modification de la forme de la courbe se fera donc uniquement par
l'intermédiaire des points du polygone, et l'utilisateur n'a pas connais-
sance de la représentation interne (ici on a choisi des polynomes).
L'expérience a montré qu'il était aisé de se familiariser avec ce mode
de manipulation.
<figure><img src="image_3.png" /><figcaption>Figure 2 : famille de fonctions $\binom{m}{i} u^i (1-u)^{m-i}$ pour m=5</figcaption></figure>
## 2.2. Surfaces Unisurf

L'extension de la méthode aux surfaces se fait aisément : une portion de surface sera définie à l'aide d'une grille de points, qui seront notés $f^*(\frac{i}{m}, \frac{j}{n})$, l'équation (1) devenant

$$f(u,v) = \sum_{i=0}^{m} \sum_{j=0}^{n} f^*(\frac{i}{m}, \frac{j}{n}) \cdot J_{m,i}(u) \cdot J_{nj}(v) \quad (3)$$

Dans ce cas, seuls les quatre points aux extrémités de la grille appartiendront à la surface (il s'agit des points $f*(\frac{0}{m}, \frac{0}{n})$, $f*(\frac{m}{m}, \frac{0}{n})$, $f*(\frac{m}{m}, \frac{n}{n})$ et $f*(\frac{0}{m}, \frac{n}{n})$).

Le fait d'avoir un produit $J_{n,i} \times J_{n,j}$ amènera une modification $\delta$ sur le point $f*(\frac{i}{m}, \frac{j}{n})$ à se répercuter en $\frac{1}{9} \times \delta$ sur le point $f(\frac{i}{m}, \frac{j}{n})$ de la surface.

La figure 3 donne des exemples de surfaces obtenues, la figure 4 montrant l'influence des différents points sur les caractéristiques de la surface sur ses frontières, ce qui indique les différentes séries de points sur lesquels il faut agir lors du raccordement de deux carreaux suivant que l'on désire assurer les continuités à l'ordre 1, 2 etc... (voir à ce sujet BEZIER [4,5] et FORREST [13]).
<figure><img src="image_4.png" /><figcaption>Figure 3 : Exemples de surfaces Unisurf avec leurs polyhèdres de définition</figcaption></figure>
<figure><img src="image_5.png" /></figure>

Figure 4 ; Exemple illustrant l'influence des points du quadrillage
sur la forme de la courbe

● points ayant une influence sur le paramètre

o points ayant une influence sur les pentes (aux frontières)

x points ayant une influence sur les courbures (aux frontières)

(tous ces points ont évidemment une influence sur la
forme de la surface).
### 3. Méthode de RIESENFELD

Récemment, RIESENFELD a proposé une modification de la méthode de BEZIER, de façon à obtenir (entre autres) des courbes plus proches des polygones que les courbes unisurf. Ces courbes sont connues également sous le nom de courbes RB³ (Riesenfeld B-spline modification to the Bézier-Bernstein technique). La formule de base reste la même que précédemment (formule (1)) mais les polynomes de BERNSTEIN sont remplacés par des B-splines.

#### 3.1. Etude des B-splines

**Définition** : Soit $(x_0, \dots, x_n)$ une suite de réels tels que $x_i \le x_{i+1}$, une fonction S est appelée fonction spline-polynomiale de degré $m-1$ si elle répond aux deux conditions suivantes :

1. S est un polynome de degré $m-1$ sur chaque intervalle $[x_i, x_{i+1}]$

2. $S \in C^{(m-2)}$, c'est-à-dire que S et ses dérivées d'ordre 1, 2, ..., $m-2$ sont continues sur tout l'intervalle $[x_0, x_n]$

Il existe plusieurs méthodes pour définir les B-splines, l'une d'entre elles consiste à utiliser une définition récursive et les différences divisées (voir De BOOR [8]). On obtient :

$$ N_{i,j}(s) = \begin{cases} 1 & \text{pour } x_i \le s \le x_{i+j} \\ 0 & \text{sinon} \end{cases} $$

$$ \text{et pour } m > 1 : \qquad N_{i,m}(s) = \frac{s - x_i}{x_{i+m-1} - x_i} \cdot N_{i,m-1}(s) + \frac{x_{i+m} - s}{x_{i+m} - x_{i+1}} \cdot N_{i+1,m-1}(s) \quad (4) $$

$N_{i,m}(s)$ est définie sur le support $(x_i, x_{(i+m \mod n)})$

La figure 5 montre les B-splines $N_{o,m}(s)$ avec $x_i = i$ (les points $x_i$ sont appelés noeuds).
<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /><figcaption>Figure 5 : B-splines</figcaption></figure>

$(N_{o,m}(x) \text{ avec } x_i = i)$
Plusieurs noeuds peuvent être confondus : on a alors des noeuds multiples. On dit que $x_i$ est de multiplicité $k_i$ si $x_i = \dots = x_{i+k_i-1} = x_{i+k_i}$.

Dans le cas de points multiples, on observe une décroissance du niveau de dérivabilité aux points multiples : si $x_i$ est de multiplicité $k_i$, les B-splines, au point $x_i$, ne seront plus dérivables que jusqu'à l'ordre $m - k_i - 1$. Ce qui fait que l'on peut obtenir des points anguleux. La figure 6 donne quelques exemples de telles fonctions. FORREST [14] a donné d'autres exemples, et RIESENFELD [16] a énuméré différentes propriétés des B-splines et leurs liens avec les polynomes de BERNSTEIN.

## 3.2 Courbes RB³

La fonction $N_{i,m}(s)$ a un seul maximum, qui est atteint en $x_{i+\frac{m}{2}}$

si $k$ est pair, et entre $x_{i+\frac{m-1}{2}}$ et $x_{i+\frac{m+1}{2}}$ si $k$ est impair. On peut donc choisir les $x_i$ de telle sorte que le maximum de $N_{i,m}(s)$ se trouve en $\frac{i}{n}$, si l'on converse la variation de $s$ entre 0 et 1.

Avec une formule du type

$$f(s) = \sum_{i=0}^{n} f^{*}\left(\frac{i}{n}\right) \cdot N_{i-\frac{n}{2}, m}(s) \quad (5)$$

La courbe $f(s)$ n'a pas ses extrémités confondues avec celles du polygone ; si l'on veut qu'elles le soient (dans le cas d'un polygone ouvert) il faut rajouter des points "fictifs" de façon à ce que $x_o$ et $x_n$ soient multiples. Si le polygone est fermé, il faut alors rajouter des points $x_{n+1} = x_o, \dots$ de façon que la courbe soit fermées elle aussi. (voir à ce sujet RIESENFELD [16]).

Les figures 7 et 8 donnent des exemples de courbes RB³ en les comparant aux courbes Unisurf.

(Par définition, les courbes RB³ sont elles aussi, des splines).
<figure><img src="image_10.png" /></figure>

$x_0 = x_1$

$m = 3$

<figure><img src="image_11.png" /></figure>

$x_1 = x_2$

$m = 3$

<figure><img src="image_12.png" /></figure>

$x_2 = x_3$

$m = 4$

<caption>Figure 6. B-splines ayant des noeuds confondus</caption>
1

<figure><img src="image_13.png" /></figure>

2

<figure><img src="image_14.png" /><figcaption>**Figure 7** : Courbes Unisurf (pointillés) et $RB^3$ (traits pleins) correspondant aux mêmes polygones (ouverts)</figcaption></figure>
<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /><figcaption>**Figure 8** : Courbes Unisurf (pointillés) et $RB^3$ (traits pleins) correspondant aux mêmes polygones (fermés)</figcaption></figure>
On voit sur ces figures (7 et 8) que les courbes $RB^3$ sont plus proche du polygone que les courbes unisurf. Pour la figure 7.1, la courbe $RB^3$ est constituée de polynômes de degré 2 (m=3) et pour la figure 7.2, il s'agit de polynômes de degré 3 (m=4).

Parmi les propriétés les plus importantes de ces courbes, on peut signaler les suivantes :

- S'il l'on modifie l'un des sommets du polygone, l'effet sur la forme de la courbe sera local, au plus m parties de la courbe seront modifiées.

- La courbe ne fera une boucle que si le polygone en fait une.

- Si m=2, la courbe et le polygone seront confondus, et si m=∞, la courbe sera une droite (ou plutôt un segment de droite).

- Si la courbe est d'ordre m, et si m sommets du polygone sont alignés, la courbe contiendra un segment de droite (coïncidant avec une portion de polygone).

- Lorsque l'on généralise le procédé aux surfaces (de la même manière que précédemment) on peut définir des carreaux ayant plus de quatre côtés, en créant des points anguleux, et on peut aussi définir des carreaux présentant des arêtes vives.
## 4. Méthode de COONS

### 4.1. Principe de la méthode

L'idée de COONS a été de proposer une formule permettant de déduire l'équation d'un carreau à partir de l'équation de ses courbes frontières, sans tenir compte de la façon dont sont définies ces courbes.

Les notations utilisées par la suite sont résumées dans le schéma ci-dessous.

<figure><img src="image_17.png" /></figure>

avec

$$ 
\left[ 
\begin{array}{l}
P_{o,o} = a_o(o) = b_o(o) \\
P_{o,1} = a_o(1) = b_o(1) \\
P_{1,1} = a_1(1) = b_1(1) \\
P_{1,o} = a_o(1) = b_1(o)
\end{array}
\right.
$$

La formule de COONS est :

$$ f(u,v) = \sum_{i=0}^{1} a_i(u) \cdot F_i(v) + \sum_{i=0}^{1} b_i(v) \cdot F_i(u) - \sum_{i=0}^{1} \sum_{j=0}^{1} P_{i,j}(u) \cdot F_j(v) \quad (6) $$

Les fonctions $F_o$ et $F_1$ sont des fonctions scalaires.

$$ F_i(j) = \delta_i^j \quad (i,j \in \{0,1\}) \quad (7) $$

$\delta_i^j$ étant le symbole de KRONECKER, on voit que l'on aura

$$ f(o,v) = b_o(v) $$

$$ f(1,v) = b_1(v) $$

$$ f(u,o) = a_o(u) $$

$$ f(u,1) = a_1(u) $$

Donc, le carreau contient ses courbes-frontières.

Pour préciser le rôle des fonctions $F_i$, on peut examiner l'un des termes de l'équation (6).

$$ \text{On a : } \sum_{i=0}^{1} a_i(u) \cdot F_i(v) = a_o(u) \cdot F_o(v) + a_1(u) \cdot F_1(v) $$

Pour $v=0$, ce terme se réduit à $a_o(u)$ et pour $v=1$, il se réduit à $a_1(u)$ à cause de la propriété des fonctions $F_i$ (7).
Les fonctions $F_i$ servent donc à former une somme pondérée de $a_o$ et $a_l$ qui varie de $a_o(u)$ à $a_l(u)$ lorsque v passe de 0 à 1. Elles "mélangent" les fonctions $a_o$ et $a_l$ (ou $b_o$ et $b_l$) ce qui explique leur dénomination anglaise : blending functions.

le terme $\sum_{i=0}^{l} a_i(u) \cdot F_i(v)$ représente donc l'équation d'une surface joignant la courbe $a_o$ à la courbe $a_l$.

De même $\sum_{i=0}^{l} b_i(v) \cdot F_i(v)$ est celle d'une surface joignant $b_o$ à $b_l$ et $\sum_{i=0}^{l} \sum_{j=0}^{l} P_{i,j}(u) \cdot F_i(u) \cdot F_j(v)$ est celle surface passant par les quatre points $P_{i,j}(u,v) \in \{0,1\}$.

Ces fonctions $F_o$ et $F_l$ seront détaillées plus loin.

## 4.2. Raccordement des carreaux

La technique de COONS est intéressante lorsque l'on étudie le raccordement de deux carreaux : le mode de définition permet en effet d'obtenir des relations indépendantes du type d'équation choisi pour représenter les ocurbes frontières.

Dans ce qui suit, la notation $f_u(u,v)$ sera utilisée pour désigner la dérivée partielle de f par rapport à u, et de manière générale,

$f_u n_v m(u,v)$ signifiera que l'on a dérivé n fois par rapport à u et m fois par rapport à v.

Considérons 2 carreaux, d'équations $f(u,v)$ et $g(u,v)$ ayant une frontière commune, comme indiqué sur le schéma ci-dessous.

<figure><img src="image_18.png" /></figure>
En général, il y aura discontinuité de la tangente, à travers la frontière commune, à moins d'introduire de nouvelles conditions sur les fonctions. COONS, dans [7], a montré que si $F_i'(o)$ (dérivée de $F_i$) était nulle, alors

$$f_u(1,0) = g_u(0,0)$$
et

$$f_u(1,1) = g_u(0,1)$$

étaient des conditions suffisantes pour que l'on ait

$$f_u(1,v) = g_u(0,v)$$

On voit donc que pour deux carreaux soient raccordés avec une continuité à l'ordre 1 sur toute la linge commune, il suffit d'assurer la continuité aux deux extrémités de la frontière.

### 4.3. Surface de correction

Les surfaces obtenues à l'aide de la formule (6) présentent quelques insuffisances, et, en particulier, la forme de l'intérieur du carreau est entièrement déterminée par la forme de ses frontières. C'est pourquoi COONS a introduit une surface dite de "correction de pente" qui vient se superposer à la première et qui permet, par l'intermédiaire des dérivées à travers les frontières, de modifier la forme intérieure du carreau.

L'équation de correction ressemble à (6) ; elle est :

$$g(u,v) = \sum_{i=0}^{l} f_u(i,v) \cdot G_i(u) + \sum_{i=0}^{l} f_v(u,i) \cdot G_i(v) - \sum_{i=0}^{l} \sum_{j=0}^{l} f_{uv}(i,j) \cdot G_i(u) \cdot G_j(v) \quad (9)$$

Les fonctions $G_i$ ayant les propriétés suivantes

$$G_i(j) = 0 \quad \forall i,j$$

$$G_i'(j) = \delta_i^j$$

Les propriétés de raccordement restent inchangées, et peuvent être étendues (pour la généralisation des corrections aux ordres supérieurs voir COONS [7]).
L'écriture sous forme matricielle permet d'observer certains aspects de l'équation de la surface corrigée. On a :

<table><tr><td>f(u,v)=-[-1 F<sub>o</sub>(u) F<sub>l</sub>(u) G<sub>o</sub>(u) G<sub>l</sub>(u)] x</td><td><table><tr><td>0</td><td>f(u,0) f(u,1)</td><td>f<sub>v</sub>(u,0) f<sub>v</sub>(u,1)</td></tr><tr><td>f(0,v)</td><td>f(0,0) f(0,1)</td><td>f<sub>v</sub>(0,0) f<sub>v</sub>(0,1)</td></tr><tr><td>f(1,v)</td><td>f(1,0) f(1,1)</td><td>f<sub>v</sub>(1,0) f<sub>v</sub>(1,1)</td></tr><tr><td>f<sub>u</sub>(0,v)</td><td>f<sub>u</sub>(0,0) f<sub>u</sub>(0,1)</td><td>f<sub>uv</sub>(0,0) f<sub>uv</sub>(0,1)</td></tr><tr><td>f<sub>u</sub>(1,v)</td><td>f<sub>u</sub>(1,0) f<sub>u</sub>(1,1)</td><td>f<sub>uv</sub>(1,0) f<sub>uv</sub>(1,1)</td></tr></table> x</td><td><table><tr><td>-1</td></tr><tr><td>F<sub>o</sub>(v)</td></tr><tr><td>F<sub>l</sub>(v)</td></tr><tr><td>G<sub>o</sub>(v)</td></tr><tr><td>G<sub>l</sub>(v)</td></tr></table></td></tr></table>

Si l'on regarde la matrice centrale, on voit que les quatre dernières lignes et colonnes sont constituées des valeurs de $f(u,v)$ $f_u(u,v)$, $f_v(u,v)$ et $f_{uv}(u,v)$ aux quatre extrémités du carreau.

### 4.4. Forme polynomiale

La plupart des applications de la méthode de COONS ont été faites en utilisant des polynomes de degré 3 pour $F_i$ et $G_i$, et également pour représenter l'équation d'une courbe.

De plus l'équation des frontières est définie à partir des coordonnées des sommets, et des valeurs des dérivées aux sommets, c'est-à-dire que, par exemple, $f(0,v)$ ne sera fonction que de $f(0,0)$ $f(0,1)$ $f_v(0,0)$ et $f_v(0,1)$. On arrive alors à une équation du carreau qui est simplifiée et qui est : (c.f. COONS)

<table><tr><td>(11) f(u,v) = [F<sub>o</sub>(u) F<sub>l</sub>(u) G<sub>o</sub>(u) G<sub>l</sub>(u)]</td><td><table><tr><td>f(0,0)</td><td>f(0,1)</td><td>f<sub>v</sub>(0,0)</td><td>f<sub>v</sub>(0,1)</td></tr><tr><td>f(1,0)</td><td>f(1,1)</td><td>f<sub>v</sub>(1,0)</td><td>f<sub>v</sub>(1,1)</td></tr><tr><td>f<sub>u</sub>(0,0)</td><td>f<sub>u</sub>(0,1)</td><td>f<sub>uv</sub>(0,0)</td><td>f<sub>uv</sub>(0,1)</td></tr><tr><td>f<sub>u</sub>(1,0)</td><td>f<sub>u</sub>(1,1)</td><td>f<sub>uv</sub>(1,0)</td><td>f<sub>uv</sub>(1,1)</td></tr></table></td><td><table><tr><td>F<sub>o</sub>(u)</td></tr><tr><td>F<sub>l</sub>(u)</td></tr><tr><td>G<sub>o</sub>(u)</td></tr><tr><td>G<sub>l</sub>(u)</td></tr></table></td></tr></table>

Et, en remplaçant $F_i$ et $G_i$ par des polynomes de degré 3 (dont on peut voir les courbes représentatives sur la figure 9) on obtient :

$$f(u,v) = [u^3 u^2 u \ 1] M C_M^t \begin{bmatrix} v^3 \\ v^2 \\ v \\ 1 \end{bmatrix} \quad (12)$$

$$\text{où M est la matrice} \begin{bmatrix} 2 & -2 & 1 & 1 \\ -3 & 3 & -2 & -1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix}$$
<figure><img src="image_19.png" /><figcaption>Figure 9 : Fonctions Fᵢ et Gᵢ choisies comme étant des polynomes de degré 3</figcaption></figure>
$t_M$ est la transposée de M

et C est la matrice (4 x 4) de l'équation (11) (c'est une matrice de vecteurs).

Dans la matrice C, il y quatre éléments pour lesquels il est difficile
de voir l'influence sur la forme de la surface : ce sont les éléments $f_{uv}(i,j)$.
Pour fixer leurs valeurs, on utilise parfois certaines techniques, qui sont
présentées en Annexe (A.1).
## 5. Manipulation de volumes

Les techniques qui ont été présentées ci-dessus, ont donné lieu à de nombreuses applications dans l'industrie, dans des domaines très divers : automobile (carosseries), industrie navale (coque de navire), aéronautique (carlingues, voilures). Cependant elles n'ont pas encore pu être intégrées dans les systèmes permettant la manipulation d'assemblages complexes d'objets (les surfaces définissant alors les enveloppes des objets).

Dans les études qui ont été faites sur la manipulation des volumes, en particulier par BRAID [6], on ne peut, actuellement réaliser que des assemblages (ou compositions) complexes d'objets élémentaires tels que le cube, le cylindre ou le cône ; ces éléments simples étant les seuls sur lesquels on sait faire les opérations nécessaires à la manipulation des volumes.

### 5.1. Opérations sur les volumes

Il y a principalement 2 opérations que l'on doit pouvoir réaliser sur les volumes : ce sont

- La **fusion** de deux objets en un seul,

- La **coupe** d'un objet par un plan ou par une surface plus complexe (ce qui mène à l'intersection de deux objets).

a) La **fusion** de deux objets peut être résumée à l'aide d'une "formule" ayant la forme suivante

<figure><img src="image_20.png" /></figure>
Une fois que la fusion a eu lieu, on obtient un seul objet, et non
un ensemble de deux objets.

La fusion peut avoir à être effectuée sur des objets dont l'un
(ou les deux) est "négatif" : la fusion d'un cube positif et d'un cylindre
négatif donnant alors un cube percé.

b) L'intersection de deux objets permet, entre autres, de découper des tranches dans des objets, et d'obtenir de nouveaux éléments pour batir l'assemblage. Elle est également très utile lorsque l'on recherche à savoir si la pièce batie n'a pas certaines de ses parties qui se touchent ou qui occupent une même portion d'espace (ce qui donne évidemment des pièces impossibles à matérialiser).

5.2. Définition des enveloppes des objets

Pour définir ses objets, BRAID a choisi une définition par faces :
un cube, par exemple, est défini par six faces planes, dont les normales
indiquent, suivant les orientations si les objets sont "positifs" ou
"négatifs". On peut envisager de conserver ce type de définition, en
définissant les faces à l'aide de fonctions biparamétriques polynomiales,
mais on se heurte rapidement à d'importants problèmes provenant de la
nature même de ces fonctions.

La première difficulté provient du fait que l'on ne sait pas
travailler sur les polynomes d'ordre élevé en utilisant d'autres méthodes
que les techniques numériques, et lorsque l'on cherche l'intersection
d'un carreau et d'un plan, on obtient une suite de points, pouvant
appartenir à plusieurs courbes différentes, et il est parfois difficile
de trouver des équations de courbes passant par ces points ou
approximant les courbes d'intersection. Le type de problème que l'on
a à résoudre pour trouver les intersections d'une surface (de degré n en u
et m en v) avec un plan est le suivant :

trouver l'ensemble des couples (u,v) vérifiant

$$
[u^n \dots 1] M \begin{bmatrix} v \\ \vdots \\ 1 \end{bmatrix} = 0
$$

où M est une matrice n x m
Ce problème ne peut être résolu, dans le cas général, et les solutions numériques ne donnent que quelques uns des couples, qu'il faut ensuite réordonner suivant les courbes auxquelles ils appartiennent.

Si l'on suppose que l'on a réussi à réordonner les points (ce qui peut être fait en utilisant le dialogue graphique par exemple), on voit apparaître un autre problème : les polynômes nécessaires à l'approximation peuvent être de degré élevé, et lorsque l'on utilise les courbes d'intersection pour définir de nouveaux carreaux, on risque d'obtenir, en fin de définition d'un objet, des expressions de degré trop élevé. On peut tenter de découper le carreau sur lequel on a fait l'intersection en carreaux plus petits, jusqu'à ce que la courbe d'intersection puisse être approximée, par morceaux, par des polynômes de bas degré avec une précision satisfaisante (la précision nécessaire étant extrêmement variable selon les applications). Dans ce cas, on finit par avoir un nombre de carreaux qui croit très vite, et cela pose alors des problèmes de temps de calcul et de taille de la base de données.

Il semble que l'on soit donc, malgré les deux derniers inconvénients qui viennent d'être signalés, contraints à se limiter à des surfaces d'ordre 2 x 2, et peut être 3 x 3, et qu'une automatisation totale soit difficilement envisageable, ce qui signifie que le concepteur aura à intervenir souvent pour aider les algorithmes, à moins évidemment, de trouver une autre méthode pour représenter les volumes.
# 6. Réalisation d'un programme interactif

## 6.1. Principes généraux

Un programme a été écrit, principalement dans le but d'étudier les problèmes d'interaction dans le cas de manipulation des surfaces. Les problèmes liés à l'intersection ont donc été ignorés et la représentation mathématique choisie pour les carreaux a été la représentation par équations polynomiales bicubiques-rationnelles. Dans tout ce qui suit, il sera donc question de carreaux ayant 4 équations parallèles : x(u,v), y(u,v), z(u,v) et h(v,u), les coordonnées réelles d'un point associé à un couple (u,v) étant

$$x(u,v) = \frac{x(u,v)}{H(u,v)} \quad y(u,v) = \frac{y(u,v)}{h(u,v)} \quad z(u,v) = \frac{z(u,v)}{h(u,v)}$$

Les coordonnées homogènes ont été choisies de façon à permettre une assez grande variété de formes, ainsi que pour traiter de manière identique toutes les transformations (translation, rotation,...).

Il n'a été fait aucun choix a priori sur la technique de manipulation de surfaces, l'utilisateur pouvant choisir, au cours de l'exécution, entre la méthode de COONS et la méthode de BEZIER. La technique de RIESENFELD, étant très proche, du point de vue du dialogue, de cette dernière, n'a pas été implémentée.

Ce programme permet de créer des carreaux, de modifier des carreaux et de connecter des carreaux. La **création de carreaux** se fait à partir de formes de bases (rectangle, demi-sphère, demi-cône, ou quart de tore). L'utilisateur entrant les paramètres fixant la taille et les proportions du carreau. La **modification** se divise en deux parties : l'application de transformations (rotations, changements d'échelle et translations) sur le carreau, et modification de la forme du carreau en utilisant différentes techniques (voir fig. 10). La **connexion de deux carreaux** permet de venir faire coïncider un côté d'un carreau sur un côté d'un autre carreau, après spécification du degré de continuité désiré (0 ou 1 dans le cas présent).
<figure><img src="image_21.png" /><figcaption>Figure 10 : Diagramme d'états du programme</figcaption></figure>
L'organisation du programme a été décrite sous forme de diagramme d'états, en vue d'une réalisation ultérieure utilisant le compilateur L.S.I. décrit dans [ 9 ] (voir Fig. 10). La version réalisée à l'aide de Fortran-3D [17] a été écrite en respectant cette structure du programme. Les paragraphes suivants présenteront quelques problèmes rencontrés, et quelques techniques utilisées pour réaliser le programme.

## 6.2. Correspondance COONS-BEZIER

### 6.2.1. Expression matricielle de l'équation de BEZIER

De même que la formule de COONS peut être exprimée sous une forme matricielle (12), du type :

$$f(u,v) = \text{UMC}^{t_M} \text{tV}^{t_V} \quad (14)$$

(où U est la matrice $[u^3 \ u^2 \ u^1]$ et $tV$ la matrice $\begin{bmatrix} v^3 \\ v^2 \\ v \\ 1 \end{bmatrix}$),

La formule de BEZIER (3) peut être mise sous une forme du même type :

$$f(u,v) = U \ N \ B^{t_N} \ t_V^{t_V} \quad (15)$$

où $N$ et $t_N$ sont des matrices constantes et $B$ est la matrice :

$$\begin{bmatrix} \text{foo} & \text{fo1} & \text{fo2} & \text{fo3} \\ \text{f10} & \text{f11} & \text{f12} & \text{f13} \\ \text{f20} & \text{f21} & \text{f22} & \text{f23} \\ \text{f30} & \text{f31} & \text{f32} & \text{f33} \end{bmatrix} \quad (16)$$

en développant la formule (3), on trouve que :

$$N = t_N = \begin{bmatrix} -1 & 3 & -3 & 1 \\ 3 & -6 & 3 & 0 \\ -3 & 3 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \quad (17)$$

### 6.2.2 Formules de changement de matrice

Le rapprochement des expressions (14) et (15) montre qu'il est simple de passer de la matrice $C$ d'un carreau à sa matrice $B$ (et vice-versa), en effet, les matrices $M$ et $V$ étant inversibles, les formules de changement de
matrice sont les suivantes :

$$
B = (N^{-1}M) C^t (N^{-1}M) \quad (18)
$$

$$
C = (M^{-1}N) B^t (M^{-1}N) \quad (19)
$$

Le calcul de ces matrices donne des résultats très simples qui sont :

$$
(N^{-1}M) = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 0 & 1/3 & 0 \\ 0 & 1 & 0 & -1/3 \\ 0 & 1 & 0 & 0 \end{bmatrix} \quad \text{et} \quad (N^{-1}M)^{-1} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ -3 & 3 & 0 & 0 \\ 0 & 0 & -3 & 3 \end{bmatrix} \qquad (20)
$$

Lorsque l'on regarde la formule C = f(B), on peut retrouver certains résultats
classiques :

$$
C = \begin{bmatrix}
f_{00} & f_{03} & | & 3(f_{01}-f_{00}) & 3(f_{03}-f_{02}) \\
& f_{30} & f_{33} & | & 3(f_{31}-f_{30}) & 3(f_{33}-f_{32}) \\
& & & & & \\
3(f_{10}-f_{00}) & 3(f_{13}-f_{03}) & | & 9(f_{00}-f_{10}+f_{11}-f_{01}) & 9(f_{13}-f_{03}+f_{02}-f_{12}) \\
& & & & & \\
3(f_{30}-f_{20}) & 3(f_{33}-f_{23}) & | & 9(f_{20}-f_{30}+f_{31}-f_{21}) & 9(f_{33}-f_{23}-f_{22}-f_{32})
\end{bmatrix} \quad (21)
$$

On retrouve une propriété des polygones de BEZIER qui est que le premier côté du polygone vaut 1 tiers de la dérivée initiale et le dernier côté vaut 1 tiers de la dérivée finale (le long d'une courbe frontière). On retrouve également le fait que les sommets $f_{11}$, $f_{12}$, $f_{21}$, et $f_{22}$ n'ont pas d'influence sur le périmètre de la courbe car ils n'interviennent dans (21) que dans les expressions des dérivées croisées de la matrice de COONS.
## 6.3 Interactions

### 6.3.1 Comparaison des deux méthodes

Avec le matériel utilisé pour réaliser le programme (IRIS 80 en time-sharing), on voit que les principaux problèmes proviennent du temps nécessaire à l'affichage d'un carreau (environ 30 sec) beaucoup plus élevé que le temps nécessaire au calcul d'une tabulation d'un carreau (moins d'1 sec). Il faut donc éviter que l'utilisateur ait trop à procéder par tatonnement pour donner à un carreau la forme qu'il désire, et par conséquent il doit pouvoir prédire le mieux possible quelles seront les répercussions de ses actions. Dans ces conditions, la méthode de Bezier se révèle plus agréable à utiliser, car comme on l'a vu précédemment (§ 2.2), avec peu d'entrainement, l'utilisateur réussit à établir convenablement le lien entre la modification faite sur le polygone et sa répercussion sur la surface. Ceci est vrai surtout en ce qui concerne la manipulation de l'intérieur de la surface. Sur la Figure 11, on voit que si l'on manipule l'intérieur d'un carreau par la méthode des quatre-points, de coons (cf. Annexe A1), la surface se déforme de façon complexe : le fait de déplacer un point, sur un carreau initialement plat, introduit quatre bosses sur la surface (au lieu d'une seule par la méthode de Bezier) ce qui fait que le lien entre la modification introduite et sa répercussion sur la surface est beaucoup plus complexe que dans la méthode de Bezier, et donc l'utilisateur peut plus difficilement prédire la répercussion de ses actions. Cependant l'utilisation de la méthode de Coons devient plus intéressante lorsqu'il faut (Figure 11) donner aux carreaux des formes telles que demi-sphère ou quart de tore, car à ce moment là il est nécessaire d'utiliser les polynomes bicubiques-rationnels, et donc de travailler en coordonnées homogènes, et par la méthode de Bezier il est assez complexe de manipuler la quatrième coordonnée.
<figure><img src="image_22.png" /><figcaption>(c)</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>**Figure 11** : Effet de la modification d'un point sur un rectangle quand on utilise la méthode de COONS.</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>Demi sphère (polynomes bicubiques-rationnels)</figcaption></figure>

<figure><img src="image_25.png" /></figure>
### 6.3.2 Interactions en trois dimensions

Le second problème qui se pose dans le dialogue utilisateur surface est dû au fait qu'il faut manipuler des objets tridimensionnels à l'aide d'appareils ne connaissant que deux dimensions, tous les appareils travaillant sur des écrans plans. Les appareils décrits, dans [18] par Newell, et qui permettent de travailler dans l'espace et non dans le plan, ne sont qu'expéri-mentaux. Il faut donc avoir recours à des artifices, tels que le travail sur 3-vues pour permettre à l'utilisateur de montrer des points plutôt que de donner leur nom. Cette méthode fournie par la version Mitra-15 du FORTRAN-3D, a été utilisée pour écrire un programme déformant un carreau par la méthode de Bezier.

Les Figures 12-a à 12-i montrent des résultats obtenus par ce programme et visualisées sur un Tektronix. Sur la figure 12-b, on voit le carreau de départ (carreau plat) et son polygone (5 × 5) est visualisé en 12-a. La figure 12-c montre la visualisation du polygone sur 3 vues ainsi qu'en perspective l'utilisateur entre alors des coordonnées sur deux des vues, le logiciel Fortran 3D déterminant alors les coordonnées X,Y,Z entrées, et matérialisant un point par une étoile : Figure 12-d. Sur cette dernière figure, les points entrés en deux dimensions sont 1 et 2 le point 3 étant le point déduit. A l'aide des coordonnées entrées, le programme détermine alors quel point du polygone a été désigné, et il reste ensuite à l'utilisateur à indiquer la nouvelle position de ce point : Figure 12-e. Sur 12-f, on voit le nouveau polygone (superposé au précédent).

La figure 12-g montre la visualisation des paramètres d'affichage suivant :
- position de l'observateur,
- point observé,
- pyramide de vision.

L'utilisateur peut modifier également ces paramètres en travaillant toujours sur 2 des 3 projections orthogonales.

Les figures 12-h et 12-i montrent enfin la répercussion des actions de l'utilisateur.

L'utilisation de ce programme montre que la méthode des 3 projections est assez facile à utiliser, mais il est certain qu'il serait beaucoup agréable pour l'utilisateur de disposer de moyens d'entrée en 3 dimensions tel que le Head-mounted défini dans [18].
<figure><img src="image_26.png" /><figcaption>Figure 12 : Exemple d'interaction</figcaption></figure>

<figure><img src="image_27.png" /></figure>

(b)
<figure><img src="image_28.png" /><figcaption>Figure 12 : Exemple d'interaction</figcaption></figure>

<figure><img src="image_29.png" /></figure>
<figure><img src="image_30.png" /><figcaption>Figure 12 : Exemple d'interaction</figcaption></figure>

(f)

<figure><img src="image_31.png" /></figure>
<figure><img src="image_32.png" /><figcaption>Figure 12 : Exemple d'interaction</figcaption></figure>
<figure><img src="image_33.png" /><figcaption>Figure 12 : Exemple d'interaction</figcaption></figure>

<figure><img src="image_34.png" /></figure>

(i)
## Al - Présentation de quelques techniques utilisées pour fixer les valeurs des dérivées croisées dans la méthode de COONS.

Dans la matrice C, de l'équation (11), les quatre termes $f_{uv}^{(i,j)}$ sont utilisés pour modifier la forme intérieure du carreau, sans toucher à ses propriétés aux frontières. L'influence de ces termes étant difficilement compréhensible directement, on les manipule parfois par l'intermédiaire d'autres grandeurs plus facilement reçables à la forme du carreau. Nous allons examiner ici les trois principales méthodes utilisées.

### a - Méthode dite des "deux parallèles"

On appelle ici parallèles deux courbes du carreau dont la variation se fait suivant un même paramètre (u ou v) : ce sont des isoparamétriques.

On peut imposer à un carreau de contenir deux courbes données $f(c,v)$ et $f(e,v)$, par exemple, c'est-à-dire que l'on impose quatre conditions de tangence, comme on peut le voir sur le schéma ci-contre.
Dans ces conditions, la relation entre les termes $f_{uv}^{(i,j)}$ et les $f^{(o,v)}$ termes $f_v^{(c,i)}$ et $f_v^{(e,i)}$ est la suivante :

<figure><img src="image_35.png" /></figure>

$$ \text{[A-1]} \quad \begin{bmatrix} G_o^{(c)} & G_l^{(c)} \\ G_o^{(e)} & G_l^{(e)} \end{bmatrix} \times \begin{bmatrix} f_{uv}^{(o,o)} & f_{uv}^{(o,1)} \\ f_{uv}^{(1,o)} & f_{uv}^{(1,1)} \end{bmatrix} = \begin{bmatrix} f_v^{(c,o)} & f_v^{(c,1)} \\ f_v^{(e,o)} & f_v^{(e,1)} \end{bmatrix} - \begin{bmatrix} F_o^{(c)} & F_l^{(c)} \\ F_o^{(e)} & F_l^{(e)} \end{bmatrix} \times \begin{bmatrix} f_v^{(o,o)} & f_v^{(o,1)} \\ f_v^{(1,o)} & f_v^{(1,1)} \end{bmatrix} $$

Les valeurs $f_{uv}^{(i,j)}$ sont alors calculables si c et e sont différents (ce qui implique que la première matrice de la formule est inversible).
b- Méthode dite "des quatre points"

La méthode que nous venons de voir n'est pas toujours simple à
utiliser, il est en effet assez difficile de déterminer les valeurs des
dérivées qui vont donner la forme désirée au carraau. La méthode des
quatre points par contre est mieux adaptée à la conception interactive
puisqu'elle impose à la surface de passer par 4 points donnés, pour des
valeurs de u et v données. Ce qui revient à dire que étant donnés
a,b,c, et d $\in$ [0,1], on fixe les quatre valeurs de f(a,c), f(a,d), f(b,c) et
f(b,d).

<figure><img src="image_36.png" /></figure>

la relation reliant les variations de
ces valeurs aux variations des termes
f<sub>uv</sub>(i,j) est alors la suivante :

$$
(A-2) \quad \begin{bmatrix} \Delta f_{uv}(0,o) & \Delta f_{uv}(0,1) \\ \Delta f_{uv}(1,o) & \Delta f_{uv}(1,1) \end{bmatrix} = \begin{bmatrix} G_o(a) & G_l(a) \\ G_o(b) & G_l(b) \end{bmatrix} \times \begin{bmatrix} f(a,c) & f(a,d) \\ f(b,c) & f(b,d) \end{bmatrix} \times \begin{bmatrix} G_o(c) & G_o(d) \\ G_l(c) & G_l(d) \end{bmatrix}^{-1}
$$

les $\Delta f_{uv}(i,j)$ seront calculables si $a \neq b$ et $c \neq d$

c) Méthode des surfaces polyconiques

Cette méthode consiste à imposer à toutes les isoparamétriques suivant u ou v d'être coniques. On démontre qu'il suffit pour cela que le développement de f(u,v) ne contienne pas de terme en u³.

Cette condition est vérifiée pour les courbes f(u,c) si

$$
\begin{bmatrix} 1 & 1 \end{bmatrix} \times \begin{bmatrix} f_{uv}(0,o) & f_{uv}(0,1) \\ f_{uv}(1,o) & f_{uv}(1,1) \end{bmatrix} = - \begin{bmatrix} 2 & -2 \end{bmatrix} \begin{bmatrix} f_v(0,o) & f_v(0,1) \\ f_v(1,o) & f_v(1,1) \end{bmatrix}
$$

Cette condition n'est pas assez forte pour déterminer complètement
les $f_{uv}(i,j)$, on dispose encore de "deux libertés", on peut donc imposer
en supplément que la surface contienne une courbe donnée (par exemple).

On peut également imposer aux deux familles f(u,c) et f(d,v) d'être des familles de coniques. Il reste dans ce cas "une liberté" pour fixer les valeurs des termes $f_{uv}(i,j)$, et on peut alors imposer à la surface de passer par un point f(a,b) donné pour deux valeurs a, b données des paramètres ce qui donne, pour calculer les dérivées croisées, les formules suivantes.
$$ \begin{bmatrix} f_{uv}(0,0) & f_{uv}(0,1) & f_{uv}(1,0) & f_{uv}(1,1) \end{bmatrix} \begin{bmatrix} G_0(a) \cdot G_0(b) \\ G_0(a) \cdot G_1(b) \\ G_1(a) \cdot G_0(b) \\ G_1(a) \cdot G_1(b) \end{bmatrix} = $$

$$ f(a,b) - \begin{bmatrix} F_0(a) & F_1(a) & G_0(a) & G_1(a) \end{bmatrix} \begin{bmatrix} f(0,0) & f(0,1) & f_v(0,0) & f_v(0,1) \\ f(1,0) & f(1,1) & f_v(1,0) & f_v(1,1) \\ f_u(0,0) & f_u(0,1) & 0 & 0 \\ f_u(1,0) & f_u(1,1) & 0 & 0 \end{bmatrix} \begin{bmatrix} F_0(b) \\ F_1(b) \\ G_0(b) \\ G_1(b) \end{bmatrix} $$

et

$$ f_{uv}(0,o) f_{uv}(0,1) f_{uv}(1,o) f_{uv}(1,1) \times \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \end{bmatrix} = -[2 - 2] \begin{bmatrix} f_v(0,o) f_v(0,1) f_u(0,o) f_u(0,1) \\ f_v(1,o) f_v(1,1) f_u(1,o) f_u(1,1) \end{bmatrix} $$

Les méthodes qui viennent d'être présentées, ne sont évidemment pas les seules que l'on puisse utiliser pour fixer les valeurs des termes $f_{uv}(i,j)$ une fois que le périmètre du carreau est défini, il convient de trouver des méthodes adaptées au problème particulier que l'on cherche à traiter lorsque l'on met en application la technique de COONS.

(Ces méthodes ont été détaillées par COONS dans [19]).
[1] ADAMS J.A.
Geometric Concepts for Computer Graphics,
U.S. Naval Academy Annapolis, Maryland, 1972

[2] ADAMS J.A.
The Intrinsic Method for Curve definition,
Computer Aided Design, Vol 7, n° 4, pp. 243-249, octobre 1975

[3] AHUJA
An Algorithm for Generating spline-like curve,
IBM Syst. J<sub>al</sub>, Vol 7, n° 3 & 4, pp. 206-217, 1968.

[4] BEZIER P.
Procédé de définition numérique des courbes et des surfaces
non mathématiques,
Automatismes n° 5 T XIII pp. 189-196, mai 1968.

[5] BEZIER P.
Emploi des machines à commande numérique,
Masson et Cie - Eyrolles, 1970.

[6] BRAID I.C.
Designing with volumes
Cantab Press, Cambridge, England, 1973.

[7] COONS S.A.
Surfaces For Computer- Aided design of Spaces Forms,
MIT Rapport MAC-TR-41, Juin 1967.

[8] DE BOOR C.
On Calculating with B-splines
J<sub>al</sub> Approximation Theory, Vol n° 6, pp. 50-62.

[9] DUCROT A.
Principes d'organisation et de réalisation du système graphique interactif
GIPSY.
Thèse de 3e cycle université de LILLE 1 Mai 1974.
[10] FERGUSON J.
Multivariate Curve Interpretation,
J<sup>al</sup> of the A.C.M., Vol. 11, n° 2, pp. 221-118, avril 1964.

[11] FORREST A.R.
Curves and Surfaces for Computer Aided Design,
Phd. Thesis, University of Cambridge, (U.K.), 1968.

[12] FORREST A.R.
On COONS and Other Methods for the Representation of Curved Surfaces,
Comp. Graphics & Image processing n° 1, pp. 341-359), 1974.

[13] FORREST A.R.
Interactive Interpolation and Approximation by Bezier Polynomials,
Computer J<sup>al</sup>, Vol 15, n°1, pp. 71-79, 1972.

[14] FORREST A.R.
A new Curve Form for Computer Aided design,
University of Cambridge, C.A.D. Group Document n° 66, 1972.

[15] GORDON W.J. & RIESENFELD R.F.
Bernstein-Bezier Methods for the computer Aided design of free-form
Curves and Surfaces
J<sup>al</sup> of the A.C.M., Vol 21, n° 2, pp. 293-310, avril 1974.

[16] RIESENFELD R.F.
Application of B-spline Approximation to Geometric Problems of
Computer Aided design,
Phd. Thesis, Syracuse University, University of Utah :
UTEC-CSC-73-126, mars 1973.

[17] SALTEL E.
Utilisation de la génération dynamique et des procédures graphiques dans le
software METAVISU III,
Thèse de 3e cycle université Paris VI, mai 1974.
[18] BARNHILL R.E. & RIESENFELD R.F.
Computer Aided Geometric Design,
Academic Press,
Articles présentés à une conférence à l'Université de Utah, 1974.
(COONS, FORREST, BARNHILL, GREGORY, DERMOTT, GORDON, RIESENFELD, BEZIER,....).

[19] Cours de l'Ecole d'Eté de l'Université du Michigan, en juin 1974,
Computer Graphics,
(COONS, VANROEKEL, HERZOG, VALLE, ...).

[20] Conférence organisée par le C.A.D. center de Cambridge, 1972,
(FORREST, SABIN, ARMIT, BEZIER, NEWELL,...).