Arnaud Dessombz

Emmanuel Letavernier

Jean-Philippe Haymann

Dominique Bazin

Michel Daudon

Calcium Phosphate Stone Morphology Can Reliably Predict Distal Renal Tubular Acidosis

Keywords: kidney, nephrolithiasis, calcium phosphate, acidosis, renal tubular, diagnosis

Purpose: Calcium stones represent 85% to 90% of all urinary calculi, including various crystalline compositions and etiological conditions. Calcium phosphate accounts for 10% to 15% of cases. These stones are mainly related to 3 groups of risk factors, including calcium or phosphate metabolism disturbance, renal acidification defects and urinary tract infection. Identifying the stone etiology often requires extensive metabolic evaluation. We assessed whether stone analysis including morphological typing in addition to stone composition could be a valuable help for diagnosis. Materials and Methods: Of 60,564 stones analysed by morphological examination and infrared spectroscopy at our laboratory 6,439 (10.6%) were mainly composed of carbapatite. Of these stone 1,093 patients were included in study who had an available etiological diagnosis and stones containing at least 70% of calcium phosphate without struvite. Results: Of the 1,093 calcium phosphate stones 12.8% showed a peculiar morphology termed IVa2, characterized by a smooth aspect and a glazed brown yellow appearance with tiny cracks. This was associated with inherited distal renal tubular acidosis in 96.1% of cases. In contrast, the other stones of similar composition but different morphology were related to distal renal tubular acidosis in only 3.9% of cases. In addition, IVa2 stones were found in 65% of calcium phosphate stone formers associated with Sjögren syndrome and in 35% of calcium phosphate stones in patients with medullary sponge kidney. These 2 conditions are related to a mild to moderate distal acidification defect. Conclusions: Identifying IVa2 stone morphology is clinically relevant because it should prompt clinicians to search for complete or incomplete distal acidosis and initiate specific therapy to decrease recurrence.

Introduction

Nephrolithiasis is a common disease affecting more than 10% of the population in Western countries with a high recurrence rate. The annual cost in the United States was $2 billion in 2000 and it is increasing with time [START_REF] Brikowski | Climate related increase in the prevalence of urolithiasis in the United States[END_REF]. The causes are diverse, including dietary disequilibrium, urinary tract infection and metabolic disorders related to acquired or genetic diseases. Although stone classifications commonly distinguish only few chemical compounds, namely calcium, uric acid, cystine and infection stones, physical analysis may identify a wide variety of components. More than 100 mineral or organic compounds have been identified to date [START_REF] Daudon | Stone composition and morphology: a window on etiology[END_REF]. In industrialized countries and in an increasing number of developing countries socalled calcium stones account for about 90% of all urinary calculi with calcium oxalate the most frequent chemical species [START_REF] Osther | Epidemiology of kidney stones in the European Union[END_REF][START_REF] Denstedt | Epidemiology of stone disease in North America[END_REF][START_REF] Luo | Epidemiology of stone disease in China[END_REF]. However, calcium stones can be divided into subgroups according to the main crystalline phase, which is often a strong marker of a specific urine composition [START_REF] Daudon | Relative influence of calcium and oxalate urine concentration on the risk of calcium oxalate crystallization[END_REF]. Of the calcium phosphate stones those of carbapatite (crystallized carbonated hydroxyapatite) may result from urinary tract infection or metabolic factors such as hypercalciuria, phosphate leak or tubular acidification defects.

Although rare, some genetic or acquired diseases may be responsible for severe forms of urolithiasis associated with nephrocalcinosis and end stage renal failure, especially when the diagnosis is delayed. For example, in primary hyperoxaluria cases stone morphology and not composition could help with the diagnosis [START_REF] Daudon | Peculiar morphology of stones in primary hyperoxaluria[END_REF]. Thus, stone morphology appears to be a convenient, straightforward and useful examination to diagnose this rare but severe pathological composition while stone composition alone does not lead to the diagnosis.

Based on this background we hypothesized that other varieties of stones could benefit from morphological examination. An example would be calcium phosphate stones, which account for 10% to 15% of all calculi and result from urinary tract infections and/ or different metabolic disorders such as idiopathic hypercalciuria, hyperparathyroidism, phosphate leak, tubular acidosis or an excessive alkali load [START_REF] Gault | Idiopathic calcium phosphate nephrolithiasis[END_REF][START_REF] Daudon | Urinary calculi: review of classification methods and correlations with etiology[END_REF].

The advantage of adding a stone morphology examination to infrared analysis is to provide a rapid, inexpensive orientation to specific pathological conditions that could not be readily identified when extensive metabolic investigations are not systematically performed. For example, in our experience the identification of typical IVa2 morphology led to the diagnosis of poorly symptomatic Sjögren syndrome with incomplete dRTA.

We sought to provide evidence that in addition to infrared spectroscopy, determining stone morphology is a key step in the diagnostic procedure of stone analysis that may identify sometimes unexpected metabolic or monogenic related stone diseases.

Patients and Methods

Of 60,564 stones analysed by morphological examination and infrared spectroscopy at our laboratory 6,439 (10.6%) were mainly composed of calcium phosphate (more than 50% of the stone mass), including carbapatite, brushite, octacalcium phosphate pentahydrate, amorphous carbonated calcium phosphate or whitlockite. Of the stones 5,181 were mainly composed of carbapatite, representing 80.5% of calcium phosphate stones and 8.5% of the whole series. Stones containing any proportion of struvite, which more specifically indicates urinary tract infection with ureolytic microorganisms, were excluded from analysis. Because Calcium phosphate may be associated with a high proportion of calcium oxalate in a number of cases and, thus, be related to various metabolic conditions, we selected only stones containing an unambiguously high proportion of calcium phosphate, namely 70% of the whole stone content on infrared spectroscopy. Finally, we included in study only calculi associated with a detailed etiological diagnosis provided by physicians, which was available for 1,093 patients.

Of the relevant diagnoses dRTA was diagnosed first based on low serum bicarbonate, moderately low arterial pH (excluding pulmonary alkalosis), low urine ammonium, urine pH greater than 6.5 and in some cases a bicarbonate load test. In addition, when measured, urine citrate was low in the absence of urinary tract infection, commonly less than 0.7 mmol per 24 hours. The diagnosis of inherited dRTA was proven by DNA sequencing of the Cl -HCO 3 exchanger gene (SLC4A1) or the H + adenosine triphosphatase gene (ATP6V0A4 or ATP6V1B1). MSK was diagnosed by computerized tomodensitometry or excretory urogram. Sjögren disease was diagnosed by at least 4 classic criteria, including a salivary gland biopsy based Chisholm score of greater than 3 and autoimmunity.

Morphological Examination and Infrared Analysis

Each calculus was studied using a stereomicroscope to define morphological type and structural characteristics as previously described.10 This also enabled the selection of representative parts of the stone for infrared analysis, such as the nucleus, the inner and external layers, and the surface [START_REF] Carpentier | Relationships between carbonation rate of carbapatite and morphologic characteristics of calcium phosphate stones and etiology[END_REF]. Spectra were recorded by a Spectrospin Vector 22 Fourier transform infrared spectrometer (Bruker, Karlsruhe, Germany). Figure 1, a shows the ½F1 typical spectra of carbapatite stones.

SEM and Statistics

A SUPRA 55-VP type environmental SEM (Carl Zeiss, Oberkochen, Germany) was used to observe the microstructure. This field effect gunmicroscope operates at 0.5 to 30 kV. High resolution observations were made using 2 secondary electron detectors, including an inlens secondary electron detector and an Everhart-Thornley secondary electron detector. An important feature of the environmental SEM compared to a conventional SEM is that nonconductive materials can be imagedwithout a conductive coating,which permits direct observation with no damage to the sample. The Fisher exact test was used for statistical comparison between groups. Statistical analysis was done with NCSS software.

RESULTS

While the infrared spectra of carbapatite stones were similar, the stones showed 2 morphological types (see Appendix and fig. 1,a to c). Stones of the first type, which was more common, had a homogenous rough surface and a poorly organized section of diffuse, whitish, concentric layers (fig. 1,b). The second type of stones showed a peculiar morphology characterized by a homogeneous smooth surface with a glazed appearance, bumps and cracks, and a heterogeneous inner organization of yellow-brown concentric foliated structures (fig. 1,c). In a previous morphoconstitutional classification of stones the 2 morphologies were termed types IVa1 and IVa2, respectively.10 The ultrastructure revealed by SEM confirmed a different stone pattern between the 2 morphological types (fig. 1, d ande). Of the 1,093 stones containing more than 70% calcium phosphate IVa1 stones were more common (87.2% of cases) than IVa2 stones. They were mainly related to chronic urinary tract infection in 39.6% of cases, hypercalciuria in 25%, MSK in 17% and primary hyperparathyroidism in 9.8% (see table 1).

Table 1. IVa1 and IVa2 types among mainly Ca phosphate calculi by etiology (p <0.0001).

In contrast, IVa2 stones, representing only 12.8% of carbapatite stones, were associated with inherited dRTA in 52.9% of cases, MSK in 35% and Sjögren syndrome in 9.3%. Thus, the specificity of IVa2 calculi for these 3 diseases was excellent at 94.3%. The IVa2 type was found in 96.1% of the 77 cases of inherited dRTA diagnosed in this series vs less than 1% of IVa1 CA stones, representing 93.5% specificity (p <0.00001). Figure 2 shows the distribution ½F2 of carbapatite stone types by etiology. In 3 cases the peculiar IVa2 stone morphology prompted us to search for inherited dRTA, which was confirmed by further metabolic evaluation. In another 3 cases the IVa2 stone morphology led to the diagnosis of Sjögren syndrome.

DISCUSSION

Kidney stones containing calcium phosphate are divided into 4 morphological types based on infrared analysis [START_REF] Daudon | Stone composition and morphology: a window on etiology[END_REF], including types IVa1 and IVa2-carbapatite, IVb-mixtures of carbapatite with other calcium or magnesium phosphates, IVc-struvite (excluded in this study) and IVd-brushite. A number of these stones are clearly distinguished by infrared analysis, for example brushite stones (IVd stones) or mixtures of various calcium and/or magnesium phosphates as in IVb stones. In the last 20 years we found a dramatic decrease in the incidence of infection stones related to urea-splitting bacteria while the proportion of IVb stones constantly decreased. Ambiguity remains for calcium phosphate stones mainly composed of carbapatite without struvite. As previously reported some of them may be related to urinary tract infection due to the high carbonate content found on infrared spectroscopy [START_REF] Levillain | Crystalline phase differentiation in urinary calcium phosphate and magnesium phosphate calculi[END_REF]. Carbapatite rich calcium phosphate stones may have 2 distinct morphologies (types IVa1 and IVa2) while the infrared spectra are often similar (fig. 1,a). We deliberately selected calculi mainly composed of carbapatite with a greater than 70% calcium phosphate level.

Figure 2. Carbapatite stone types by IVa1 and IVa2 etiology, including 0.3% and 52.9% for dRTA, 17.0% and 35.0% for MSK, 0.7% and 9.3% for Sjögren syndrome, 5.2% and 1.4% for carbonic anhydrase inhibitors (CAI ), 9.8% and 0.0% for primary hyperparathyroidism (PHPT), 25.0% and 0.0% for idiopathic hypercalciuria (IH ), 39.6% and 1.4% for urinary tract infection (UTI ), and 2.4% and 0.0% for phosphate leak, respectively. Asterisk indicates p <0.001 vs IVa1.

As noted in the current study IVa1 and IVa2 stones are associated with different pathological conditions. The main causes of IVa1 stones are those commonly reported in the literature for calcium phosphate stones, ie urinary tract infection, hypercalciuria and primary hyperparathyroidism [START_REF] Hesse | Causes of phosphate stone formation and the importance of metaphylaxis by urinary acidification: a review[END_REF][START_REF] Evan | Histopathology and surgical anatomy of patients with primary hyperparathyroidism and calcium phosphate stones[END_REF][START_REF] Lin | Clinical and prognostic characteristics of 573 cases of primary Sj€ogren's syndrome[END_REF]. In contrast, type IVa2 stones appear specific to inherited dRTA (see table ). Interestingly IVa2 calculi are not associated with proximal tubular acidosis since stones in 96.2% of patients treated with carbonic anhydrase inhibitors, which induce proximal and distal tubular acidosis, were mainly type IVa1. Thus, IVa2 stone formation seems to depend on sustained high pH in the distal part of the nephron lumen, a setting present in dRTA due to Hþ secretion defects [START_REF] Kassan | Clinical manifestations and early diagnosis of Sjögren syndrome[END_REF]. The typical metabolic acidosis profile may be missing in incomplete dRTA. Sjögren syndrome and MSK are significantly associated with high urinary pH related to incomplete distal acidosis, ie an acidification defect affecting only the distal segment of some nephrons [START_REF] Fulop | Renal tubular acidosis, Sjögren syndrome, and bone disease[END_REF][START_REF] Wrong | Immunerelated potassium-losing interstitial nephritis: a comparison with distal renal tubular acidosis[END_REF][START_REF] Higashihara | Medullary sponge kidney and renal acidification defect[END_REF]. In 1 series a distal acidification defect was observed in up to 40% of patients with MSK [START_REF] Ginalsky | Does medullary sponge kidney cause nephrolithiasis?[END_REF]. However, another study failed to show evidence of an acidification defect in a significant proportion of patients with MSK [START_REF] Fabris | Long-term treatment with potassium citrate and renal stones in medullary sponge kidney[END_REF]. In clinical practice the MSK diagnosis is difficult to assess by excretory urogram as suggested by discrepancies in the incidence of MSK in stone forming patients in the literature (range 3.5% to 21%) [START_REF] Wikstr€om | Ambulatory diagnostic evaluation of 389 recurrent renal stone formers. A proposal for clinical classification and investigation[END_REF][START_REF] Laube | Prevalence of medullary sponge kidney in patients with and without nephrolithiasis[END_REF][START_REF] Yendt | Medullary sponge kidney[END_REF]. These discrepancies are due to various criteria used to diagnose MSK. Until the recent optimization of diagnostic methods based on computerized tomography the identification of MSK anatomical defects was complex [START_REF] Gambaro | Medullary sponge kidney[END_REF]. In our experience calcium oxalate (67.4%) and calcium phosphate (26.7%) were the main component of stones in 576 patients with MSK (unpublished data). IVa2 stones were noted only in 8.2% of cases. Thus, MSK appears to be a heterogeneous entity. The previously demonstrated link between IVa2 and distal acidosis suggests that IVa2 stones in patients with MSK would be the hallmark of a local acidification defect responsible for incomplete renal tubular acidosis. In cohorts of patients with Sjögren syndrome renal involvement was estimated to be between 25% and 40%.26e28 In clinical practice it is not always easy to make the diagnosis because metabolic disorders may be absent or not specific, such as hypocitruria, which is a common finding in nephrolithiasis cases. Thus, hypocitruria is not pathognomonic for distal tubular defect because it is often found in patients with another condition such as urinary tract infection as well as in idiopathic calcium stone formers [START_REF] Pak | Citrate and renal calculi: an update[END_REF]. Moreover, Sjögren syndrome may be poorly symptomatic. In our experience identifying the typical IVa2 stone morphology led to the diagnosis in several cases.

Our series clearly shows the strong link between dRTA and IVa2. Among other etiologies we found a high rate of the IVa2 type in calcium phosphate stones in patients with Sjögren syndrome (65%) or MSK (23.2%), suggesting that patients with such a stone morphology have a defect of distal acidification. Thus, an early diagnosis first indicated by typical IVa2 stone morphology may have major clinical relevance.

The high prevalence of inherited or acquired dRTA in IVa2 stone group (136 patients or 97%) may also explain why IVa2 stones are more active and recurrent than IVa1 stones. In our series 79.8% of patients with IVa2 stones had multiple recurrent stone episodes while the recurrence rate was only 54.7% in patients with IVa1 stones (p <0.0001).

Thus, this high risk population deserves reinforced medical management that especially focuses on water and alkali intake. In contrast to IVa1 stones, no primary hyperparathyroidism, idiopathic hypercalciuria or phosphate leak (also called type III hypercalciuria) was observed in IVa2 stone cases. This provides interesting clinical clues and evidence that a high urinary calcium rate is not associated with this specific morphological type.

Our study has limitations. 1) It was based on a declarative diagnosis by physicians who completed a detailed form including all relevant diagnoses, limiting the study to 1,093 patients. 2) The MSK diagnosis is often complex. Incomplete distal tubular acidosis may be under diagnosed in the absence of an acidification test. It could be interesting to assess whether a IVa2 stone is a feature of underlying acidosis in MSK cases, which deserves further study.

CONCLUSIONS

To our knowledge our data address a new paradigm in stone disease and demonstrate the interest in stone morphology analysis in addition to composition, as recently suggested by Williams and McAteer [START_REF] Williams | Retention and growth of urinary stones: insights from imaging[END_REF]. For the patient it appears highly effective and beneficial to assess an unexpected etiology that is often responsible for recurrent calculi and/or progressive renal failure, or to link/exclude stone disease using metabolic or pathological findings. For the first time to our knowledge our study shows the strong, specific link between dRTA and carbapatite stone morphological type IVa2 irrespective of the cause of dRTA. Notably stone disease may be the most prominent sign of acquired tubular acidosis before extrarenal manifestations. In such cases stone morphology provides strong evidence of dRTA.

Thus, it allows for early diagnosis and subsequent early medical management, which helps prevent the progression of chronic kidney disease. In addition to infrared spectroscopy analysis, stone morphology appears to be a major analytical step to make an etiological diagnosis of calcium phosphate kidney stones, as previously illustrated for calcium oxalate monohydrate stones in primary hyperoxaluria cases [START_REF] Daudon | Peculiar morphology of stones in primary hyperoxaluria[END_REF]. APPENDIX Main morphological differences between IVa1 and IVa2 stone types.

Figure 1 .

 1 Figure 1. a, typical FTIR spectroscopy spectra of IVa2 and IVa1 type kidney stones. b, external and internal optical images of IVa1 type. c, external and internal optical images of IVa2 type. Arrows indicate surface cracks. d, SEM image shows type IVa1. e, SEM image shows type IVa2. d and e, scale bar indicates 10 m.


Michel Daudon
email: michel.daudon@tnn.aphp.fr

Dominique Bazin

Emmanuel Letavernier

Randall's plaque as the origin of calcium oxalate kidney stones

Keywords: Randall's plaque, Kidney stones, Calcium, Oxalate, Apatite

come

Introduction

Calcium oxalate (CaOx) stones are now identified as the main type of urinary calculi in most countries throughout the world. They account for at least 70 % of all stones developed in the upper urinary tract and even more in male patients [START_REF] Curhan | Epidemiology of stone disease[END_REF]. In some parts of the world, CaOx was found as the main component of about 90 % of all kidney stones [START_REF] Ansari | Spectrum of stone composition: structural analysis of 1050 upper urinary tract calculi from northern India[END_REF]. Such a progression in CaOx stones accounts for the increase in the prevalence of kidney stone disease frequently reported during the past decades from countries where longitudinal epidemiological surveys are available as in the United States [START_REF] Denstedt | Epidemiology of stone disease in North America[END_REF], in Europe [START_REF] Hesse | Study on the prevalence and incidence of urolithiasis in Germany comparing the years 1979 vs. 2000[END_REF][START_REF]Epidemiological trends in urolithiasis: impact on our health care systems[END_REF] or in Japan [START_REF] Ogawa | Epidemiology of stone disease over a 40-year period in Japan[END_REF]. Among the risk factors involved in stone formation, low diuresis and imbalance in diet are well documented [START_REF] Siener | Impact of dietary habits on stone incidence[END_REF][START_REF] Asselman | Fructose intake as a risk factor for kidney stone disease[END_REF][START_REF] Fung | DASH-style diet associates with reduced risk for kidney stones[END_REF]. Although a lot of inherited or acquired diseases may induce kidney stone formation, all together account for less than 10-15 % of calcium stones in the general population. Thus, most of calcium stones result from biological disorders in urine such as hypercalciuria, hyperoxaluria and/or hypocitraturia without any "identified" pathology. Moreover, these disorders are inconstantly found when urine biochemistry is performed, suggesting the anomalies are intermittent or transient, or simply related to low diuresis, which results in an increased concentration of poorly soluble salts in urine. Thus, the so-called idiopathic nephrolithiasis is the bulk of calcium stones. However, during the last decade, a series of investigations by the group of Evan, Lingeman and Coe, highlighted the role of calcium phosphate deposits in the papilla tip as a starting point of CaOx stone formation [START_REF] Van | Randall's plaque of patients with nephrolithiasis begins in basement membranes of thin loop of Henle[END_REF][START_REF] Van | Mechanism of formation of human calcium oxalate renal stones on Randall's plaque[END_REF][START_REF] Van | Contrasting histopathology and crystal deposits in kidneys of idiopathic stone formers who produce hydroxy apatite, brushite, or calcium oxalate stones[END_REF]. Such deposits, termed Randall's plaque because they were first described by Alexander Randall in the 1930s, initiate in the basement membrane of the long Henle's loops and spread out in the interstitium around the Bellini's ducts close to the papillary epithelium. When the epithelium is disrupted, the calcium phosphate deposits are in contact with the supersaturated urine issued from the vicinal nephrons, thus favouring CaOx crystallization and trapping of the crystals at the surface of the plaque. Thereafter, the stone growth is driven by urine supersaturation.

Original description of papillary calcified plaques by Randall

More than 75 years ago, Alexander Randall reported a study on "The origin and growth of renal calculi", which appeared first in the New England Journal of Medicine [START_REF] Randall | An hypothesis for the origin of renal calculus[END_REF] and the following year in the Annals of Surgery [START_REF] Randall | The origin and growth of renal calculi[END_REF]. In this seminal paper, he described a hitherto unrecognized papillary lesion consisting in calcium phosphate deposits in the intertubular spaces of the renal papilla, observed in 19.6 % of 1,154 pairs of kidneys examined at autopsy. He made three observations:

-first, this papillary lesion which appeared as a cream coloured area near the tip of the papilla was not on its surface, but was subepithelial in location; -second, the chemical composition of papillary plaques was shown to be made of calcium phosphate and carbonate;

-third, small calculi were found to be attached to plaque at the tip of papillae in 65 kidneys (2.8 %), their composition differing from that of the plaque. The stones were made of calcium oxalate; -fourth, CaOx stones collected in routine practice often exhibited a portion which was smooth and somewhat depressed, resembling a facet corresponding with the morphology of the papilla.

Examining by light microscopy some calculi actually attached on a papillary plaque, Randall found that the stone was continuous with the interstitial plaque and that the epithelial covering of papilla was lost. Such aspect of calcium phosphate deposits in the interstitium was termed papillary lesion type 1 by Randall who proposed that papillary calcium deposits could act as a nidus for urinary salt accretion if epithelial covering of the papilla is lost. Randall also found in some cases Bellini's ducts filled by calcium phosphate plugs (termed papillary lesion type 2). He suggested the phosphate plugs may be another way for CaOx stone formation.

Fig. 1 Scanning electron microscopy photographs of calcium oxalate calculi initiated from a Randall's plaque. a

The plaque is made of a mixing of tubules with calcified walls (white arrow) and of tubules obstructed by calcium phosphate plugs (black arrow). b Randall's plaque at the surface of another calcium oxalate stone with calcified tubules and a calcium phosphate plug partly obstructing the lumen of a collecting duct.

Fig. 2 Scanning electron microscopy photograph of a tubular plug (black arrow) at the origin of a calcium oxalate monohydrate stone

Scanning electron microscopy examination of CaOx stones developed from a Randall's plaque provides evidence that plaque is made of a mixing of tubules with calcified walls (white arrow, Fig. 1a) and of tubules obstructed by calcium phosphate plugs (black arrow, Fig. 1a or white arrow, Fig. 1b). Please note in Fig. 1b, the calcium phosphate cluster within the tubular lumen (white arrow), while other tubules are empty with calcified walls. In other cases, much less frequent, the nidus of the stone appears only as a tubular plug (Fig. 2, black arrow). At the time Randall performed his studies, he could not identify the exact location and nature of calcium deposits within the papillary structure. Nor, due to the forensic nature of his study material, could he evaluate urinary solute excretion in the affected individuals.

Epidemiological considerations

Other authors confirmed the findings of Randall in autopsy studies during the same period: for example, Rosenow found plaques in 22.2 % of 239 kidneys, whereas Anderson observed plaques in 12 % of kidneys in a series of 1,500 necropsies [START_REF] Rosenow | Renal calculi: study of papillary calcification[END_REF]16]. In South Africa, Vermooten [START_REF] V Ermooten | The incidence and significance of the deposition of calcium plaques in the renal papilla as observed in the Caucasian and Bantu population in South Africa[END_REF] examined 1,060 pairs of kidneys. He found Randall's plaques in 17.2 % of Caucasians and only 4.3 % of Bantus, a finding in keeping with his observation of the lower incidence of calcium nephrolithiasis in the local population of African descent than Caucasian descent. Papillary calcifications were seen in the subepithelial interstitial tissue together with collagen fibres, and were not found in the lumen of collecting ducts [START_REF] V Ermooten | Origin and development in renal papilla of Randall's calcium plaques[END_REF]. Forty years after the first description of papillary calcified deposits acting as a nidus for calcium stone formation, Luis Cifuentes-Delatte, a Spanish urologist enthusiastic for research on stone formation observed with his colleagues that 142 out of 500 consecutive calculi exhibited a concavity characteristic of a papillary origin [START_REF] Cifuentes-Delatte | New studies on papillary calculi[END_REF]. In 61 (43 %) of these umbilicated calculi, plaques were typically made of apatite, some of them showing calcified collecting ducts [START_REF] Cifuentes-Delatte | Papillary stones: calcified renal tubules in Randall's plaques[END_REF].

Fig. 3 Whewellite stone initiated from a carbapatite Randall's plaque (white arrow) Fig. 4 Mixed stone made of whewellite and weddellite nucleated from a Randall's plaque (white arrow)

In our experience, based upon 45,774 calculi referred to the Necker hospital stone laboratory over the past three decades, we found by morphologic examination coupled with FTIR analysis that 8,916 (19.5 %) calculi exhibited a depressed surface (umbilication) suggestive of a papillary attachment [START_REF] Daudon | Stone morphology suggestive of Randall's plaque[END_REF]. Most of these stones (92.5 %) were made of CaOx monohydrate (whewellite) either pure (Fig. 3) or admixed with CaOx dihydrate (weddellite) as observed in Fig. 4. As previously reported, the composition of Randall's plaque is carbapatite in 90 % of cases, but other crystalline phases may be found as main component of Randall's plaque such as amorphous calcium phosphate, brushite or whitlockite, or trioxypurines like sodium urate [START_REF] Cifuentes-Delatte | New studies on papillary calculi[END_REF][START_REF] Daudon | Stone morphology suggestive of Randall's plaque[END_REF].

However, detailed endoscopic examination of renal cavities during percutaneous nephrolithotomy (PNL) or ureteroscopic procedures suggests a much higher prevalence of Randall's plaques than that deduced from stone examination. An explanation could be that modern urological treatment to remove stones often use fragmentation techniques such as shockwaves, ultrasounds or laser. As a consequence, stone fragments collected for analysis may have lost both the part of Randall's plaque fixed to the stone and the typical depressed face. In 1997, using endoscopic procedures, Low and Stoller reported the presence of Randall's plaques on one or more papillae in 74 % of 57 stone formers, the prevalence being 88 % for CaOx stones [START_REF] Low | Endoscopic mapping of renal papillae for Randall's plaques in patients with urinary stone disease[END_REF]. In 2006, Matlaga et al. [START_REF] Matlaga | Endoscopic evidence of calculus attachment to Randall's plaque[END_REF] found that 91 % of papillae in 23 patients with idiopathic CaOx nephrolithiasis harboured plaques and half of papillae had attached calculi. Digital imaging provided undisputable evidence of stone attachment to plaque. Indeed, epidemiological differences in the occurrence of Randall's plaques may be observed according to the investigated population. Recent reports from European countries suggest that Randall's plaque could be less frequent in Europe than in the United States. In Italy, Ruggera et al. reported the occurrence of Randall's plaque in 44.4 % of 27 stone formers who underwent ureterorenoscopy or PNL and renal papillae biopsy [START_REF] Ruggera | Does Randall's plaque represent a necessary condition in the pathogenesis of the idiopathic calcium oxalate stones? In: Abstracts of the 11th international symposium on urolithiasi[END_REF]. In France, Olivier Traxer found Randall's plaques in 57 % of 287 stone formers who underwent flexible ureterorenoscopy. They were observed on all papillae in 54 % of these patients. Such plaques were visible in only 27 % of 173 non-stone forming patients [START_REF] Carpentier | Plaques de Randall: fréquence, topographie et classification[END_REF][START_REF] Daudon | Randall's plaques[END_REF].

Fig. 5 Occurrence (%) of Randall's plaque at the origin of spontaneously passed calcium oxalate stones according to the patient's age

Of note, in France, stones harbouring an umbilication were found to be three times more frequent in the recent years than at the beginning of the 1980s and patients were younger and younger [START_REF] Daudon | Épidémiologie actuelle de la lithiase rénale en France[END_REF]. Children may form CaOx stones from Randall's plaque. As shown in Fig. 5, when considering only unfragmented stones spontaneously passed or removed by urological procedures without fragmentation, the part of stones developed from a Randall's plaque is very high and dramatically increasing with age from childhood up to the age class 20-30 years, then slowly decreasing thereafter. In our experience, 39 % of all spontaneously passed stones had a typical umbilication on their surface and 5,728 among 8,662 (66.1 %) of spontaneously passed CaOx monohydrate calculi were umbilicated and were developed from a Randall's plaque.

Randall's plaques begin in basement membranes of thin Henle's loops

In an elegant study, Evan and co-workers recently provided substantial advances in the pathogenesis and structure of Randall's plaques in patients with CaOx stones [START_REF] Van | Randall's plaque of patients with nephrolithiasis begins in basement membranes of thin loop of Henle[END_REF]. They took superficial biopsy specimens from papillae in the upper, middle and lower poles of a kidney during PNL performed for stone removal in 15 patients with recurrent, idiopathic CaOx nephrolithiasis, all of whom were hypercalciuric, and in 4 patients with CaOx stones and hyperoxaluria due to jejuno-ileal bypass for obesity.

By light microscopy, they confirmed Randall's plaques to be in subepithelial position at the papillary tip, surrounding the openings of the ducts of Bellini. Calcium-containing deposits were found surrounding primarily the thin loops of Henle. Electron microscopy revealed these deposits to be located within the basement membrane of Henle's loops and around adjacent vasa recta, but not within the cytoplasm of the cells. Infrared microspectroscopy of deposits identified spectral bands characteristics of hydroxyapatite, associated with calcium carbonate in about 20 % of cases. In summary, papillary plaques are interstitial and composed of apatite, originate in the basement membrane of the thin loops of Henle and subsequently spread into the surrounding interstitium, in the vasa recta and in the basement membranes of collecting ducts, without affecting collecting duct cells themselves. As said by the authors, "the overall impression is that the basement membrane of thin limbs is indeed the origin of plaque".

In contrast, none of the four patients with enteric hyperoxaluria due to jejuno-ileal bypass exhibited such papillary plaques. Instead, they exhibited intratubular hydroxyapatite crystals in the lumen of some collecting ducts, attached to their apical surface. Thus, the site of initial crystallization differed according to the underlying metabolic abnormality. Of note, four non-stone-formers subjected to nephrectomy, taken as controls, had neither papillary plaques nor tubular crystals [START_REF] Van | Randall's plaque of patients with nephrolithiasis begins in basement membranes of thin loop of Henle[END_REF]. Looking for risk factors associated with Randall's plaque formation, Kuo et al. found that low urine output, high calcium content and low urine pH were significantly more frequent in calcium stone formers with than without Randall's plaque [START_REF] Kuo | Urine calcium and volume predict coverage of renal papilla by Randall's plaque[END_REF]. Moreover, Kim and coworkers reported that stone episodes were proportional to the coverage of papilla by Randall's plaques [START_REF] Kim | Stone formation is proportional to papillary surface coverage by Randall's plaque[END_REF].

Role of hypercalciuria in the pathogenesis of Randall's plaques

Evan and co-workers speculate that hypercalciuria should be the main explanation at the origin of Randall's plaques [START_REF] Van | Randall's plaque of patients with nephrolithiasis begins in basement membranes of thin loop of Henle[END_REF]. Before examining their arguments, one may remember that an epidemiologic case/control study identified high urinary calcium concentration to be the major risk factor for idiopathic calcium nephrolithiasis [START_REF] Curhan | Twenty-four-hour urine chemistries and the risk of kidney stones among women and men[END_REF], whereas oxalate, uric acid and citrate concentrations did not differ between incident stone formers and contemporary controls. In the study of Evan et al. [START_REF] Van | Randall's plaque of patients with nephrolithiasis begins in basement membranes of thin loop of Henle[END_REF], the mean calcium excretion was 312 mg/day (7.8 mmol/day) in the 15 CaOx stone Fig. 5 Occurrence (%) of Randall's plaque at the origin of spontaneously passed calcium oxalate stones according to the patient's age formers, compared to 113 mg/day (2.8 mmol/day, p < 0.01) in the 4 non-lithiasic controls.

According to the authors and to the editorial comments of their work by Bushinsky [START_REF] Bushinsky | Nephrolithiasis: site of the initial solid phase[END_REF], the sequence of events could be as follows. Hypercalciuria is associated with intestinal calcium absorption, which results in postprandial peaks in serum calcium, reflected in increased calcium concentration in glomerular filtrate and in the fluid presented to the thin limbs, then to the thick ascending limb. High calcium reabsorption at this site enriches the outer medulla with calcium, which is washed into the deep medulla by the descending vasa recta. The origin of calcium phosphate deposits in the interstitium may be the consequence of several mechanisms. As reported by Asplin and co-workers [START_REF] Asplin | Evidence of calcium phosphate supersaturation in the loop of Henle[END_REF], the narrow part of the long loops of Henle is often supersaturated for calcium phosphate, which may precipitate. Despite the short transit time in that part of the nephron (20-30 s), where most particles remain free in the tubular lumen, some of them may be attached to the apical cell membrane, especially if urinary macromolecules and other inhibitors such as citrate are in low concentration or if an oxidative stress was able to damage the cell surface. Then, an endocytosis process may be initiated to eliminate them by intracellular dissolution [START_REF] Lieske | Adhesion, internalization and metabolism of calcium oxalate monohydrate crystals by renal epithelial cells[END_REF]. Calcium and phosphate ions resulting from the apatite dissolution are transferred in the interstitium and may locally induce high CaP supersaturation favouring new crystallization of apatite in the basement membrane of thin limbs, which is unusually thick and is composed of collagen with abundant mucopolysaccharides. Apatite crystals, once initiated, are able to accumulate and extend in the interstitium. At the microscopic scale, Evan et al. have shown that apatite crystals are composed of successive layers of mineral and macromolecules such as osteopontin [START_REF] Van | Mechanism of formation of human calcium oxalate renal stones on Randall's plaque[END_REF]. Extensive accumulation of interstitial calcium deposits up to the papillary epithelium may result in a disruption of the epithelium by a yet poorly understood mechanism, thus making the apatite crystals exposed to the supersaturated urine. In the first following steps, new layers of calcium phosphate and macromolecules may cover the plaque, after what CaOx crystals formed in the surrounding supersaturated urine may be attached on the plaque, thus initiating stone formation [START_REF] Van | Mechanism of formation of human calcium oxalate renal stones on Randall's plaque[END_REF][START_REF] Daudon | Randall's plaques[END_REF].

As underlined by Tiselius [START_REF]The role of calcium phosphate in the development of Randall's plaques[END_REF], calcium phosphate precipitation requires high CaP supersaturation, which is favoured by high pH value, high concentration of calcium and/or phosphate ions. Indeed, the physicochemical environment in the interstitium of the inner medulla favours calcium phosphate supersaturation around the tip of Henle's loops, especially in the presence of hypercalciuria and low urine output. In case of an excessive acid load, as observed in patients who eat large amounts of animal proteins, an increased excretion of H+ ions by the collecting duct cells results in a low urine pH and an increased production of bicarbonate ions transferred to the interstitium. High protein intake is also responsible for a high excretion of phosphate ions, which could be another favouring factor for explaining calcium phosphate supersaturation in tubular lumen and the papillary interstitium.

As a result of the high acid load (the same is observed in the case of antidiuresis), the pH increases in the inner medulla, inducing supersaturation of calcium phosphate that may precipitate. Moreover, in hypercalciuric states, which appear to be more frequent in patients with Randall's plaques, a default of calcium reabsorption in the proximal part of the tubule results in an increased delivery of calcium in the distal part of the nephron, which may contribute to the supersaturation of calcium phosphate and/or CaOx [START_REF] Coe | Evidence for increased postprandial distal nephron calcium delivery in hypercalciuric stone forming patients[END_REF]. In the case of low diuresis, the hyaluronic acid content in the inner medulla decreases [START_REF] Hansell | Hyaluronan content in the kidney in different states of body hydration[END_REF] thus reducing its availability to act as an inhibitor of crystallization and results in increased concentration of solutes in the interstitium.

Fig. 6 Section of a whewellite stone exhibiting a whitish core made of carbapatite containing holes highly suggestive of Randall's plaque with calcified tubules

While endocytosis of CaP particles or secondary precipitation of CaP in the basement membrane of the cells may result from local high supersaturation, another phenomenon could explain why CaOx crystals may be secondary deposited on the CaP Randall's plaque after the papillary epithelium has been lost by a yet unexplained mechanism. Indeed, it is well known that CaP particles are the most frequent mineral phases found in urine [START_REF] Smith | Hydroxyapatite-the forgotten crystal in calcium urolithiasis[END_REF]. In the case of low diuresis or high acid load, the secretion of H+ in the distal part of the nephron results in a rapid decrease of the pH inducing dissolution of CaP particles. As a consequence, an increased calcium concentration may increase enough the CaOx supersaturation to induce nucleation of CaOx crystals that are excreted in the caliceal cavities [START_REF] Denstedt | Epidemiology of stone disease in North America[END_REF][START_REF] Sethmann | Replacement of hydroxylapatite by whewellite: implications for kidney-stone formation[END_REF] and then may be fixed on the CaP particles at the surface of the papilla [START_REF] Daudon | Randall's plaques[END_REF]. Then, the stone growth depends on the level of CaOx supersaturation, which is linked to the diuresis, and the concentration of both calcium and oxalate, and also of inhibitors such as citrate. When the stone is too large or too heavy for the mechanical resistance of the Randall's plaque that plaque may be disrupted and the stone free in the caliceal space. Thereafter, it may be rapidly spontaneously passed (the most frequent situation) or retained in the calyx.

In such case, new CaOx crystals may progressively cover the umbilication and the calcium phosphate plaque, which disappears at the surface of the stone. When removed or spontaneously expelled, the stone does not exhibit any Randall's plaque which is found in the core of the stone as suggested by Miller et al. [START_REF] Miller | In idiopathic calcium oxalate stone-formers, unattached stones show evidence of having originated as attached stones on Randall's plaque[END_REF] and illustrated in Fig. 6.

Randall's plaque and stone composition

First studies by Evan and co-workers suggest that apatite crystals are the mineral phase for interstitial plaque and that amorphous calcium phosphate (ACP) deposits may cover the plaque secondly after it outcrops at the surface of the epithelium [START_REF] Van | Mechanism of formation of human calcium oxalate renal stones on Randall's plaque[END_REF]. However, as suggested by Tiselius [START_REF]The role of calcium phosphate in the development of Randall's plaques[END_REF] ACP formation is favoured by high CaP supersaturation, which may occur not only in the urine, but also in the interstitium. In fact, other works suggest that ACP may be more abundant in the interstitial part of the Randall's plaque than at its surface [START_REF] Carpentier | The pathogenesis of Randall's plaque: a papilla cartography of Ca compounds through an ex vivo investigation based on XANES spectroscopy[END_REF]. As previously reported, Randall's plaque is made of carbapatite in most cases, but other calcium phosphates and other chemical species, such as sodium urate may be identified within Randall's plaque [START_REF] Daudon | Stone morphology suggestive of Randall's plaque[END_REF]. As shown in Table 1, about 15 different crystalline species were found among 11,016 calculi exhibiting a papillary umbilication. Carbapatite was identified in 97.6 % of cases, either pure or mixed with other calcium phosphates or other compounds such as purines. However, in some cases, carbapatite was not detected and then, another mechanism than Randall's plaque may be involved in stone formation. We cannot exclude that some of these compounds such as uric acid were only deposited at the surface of the papilla because of a local tissue lesion and then acted as a factor for heterogeneous nucleation of calcium oxalate. Of note, around the Randall's plaque the first layers of the stone are made in most cases by CaOx monohydrate [START_REF] Daudon | Stone morphology suggestive of Randall's plaque[END_REF][START_REF] Sethmann | Replacement of hydroxylapatite by whewellite: implications for kidney-stone formation[END_REF].

Conclusion

Idiopathic CaOx stones, the occurrence of which has been frequently reported as increasing during the past half century, mainly from a Randall's plaque made of carbapatite. In parallel, the progress in endoscopic material and optics, making easy the visual inspection of kidney papillae provides evidence that Randall's plaques are become very common in stone formers as in the general population. Such changes are in line with indepth modifications in dietary habits in industrialized countries over the past decades. A better knowledge regarding the mechanisms involved in the formation of calcified deposits within the inner medulla of the kidney is required in order to provide efficient advices able to reduce the occurrence of Randall's plaque and stone formation.


Stéphane Redon

Abderrahmane Kheddar

Sabine Coquillart

Gauss' Least Constraints Principle and Rigid Body Simulations

published or not. The documents may come

Gauss' least constraints principle and rigid body simulations

Introduction

Rigid body simulations have numerous offline or online applications: virtual environments, virtual prototyping, teleoperation, assembly tasks, interactive tolerance tests, video games. Many situations require the simulation of classical physics laws. This explains why rigid body simulation is such an active research field.

While moderately complex objects can be handled in real-time by the known simulation systems [START_REF] Baraff | Fast Contact Force Computation for Nonpenetrating Rigid Bodies[END_REF], complex objects may require many computations as the number of contact points increases, and the strategy is often to display complex objects while computing the simulation on simplified objects [START_REF] Fröhlich | Physically-Based Manipulation on the Responsive Workbench[END_REF]. We believe that the reason for this is that the simulation systems do not make explicit use of the number of degrees of freedom (dof) in the simulation 1 . Thus, as the average number of contact points per object increases, the simulators are not as efficient as they could be.

Note that the average number of contact points per object can increase dramatically as the objects complexity increases. Consider two contacting cubes. If the cubes are almost aligned and one cube is slightly rotated, then eight contacts occur. Now, if the cubes are replaced by n-sided polyhedral cylinders in a similar configuration, then 2n contacts occur. Other examples can easily be found: threaded screws insertion, tightlypacked objects, object clusters. Also, the fact that tolerance values are used in collision detection increases the number of contact points.

To our knowledge, most of recently proposed (constraintbased) solutions able to handle unilateral constraints formulate the dynamics problems (ie the constrained motion problem and the collision resolution problem) as a linear complementarity problem (LCP) (see for example [2] [START_REF] Baraff | Fast Contact Force Computation for Nonpenetrating Rigid Bodies[END_REF] [START_REF] Ruspini | Collision/Contact Models for the Dynamic Simulation of Complex Environments[END_REF] [START_REF] Sauer | A Constraint-based Approach to Rigid Body Dynamics for Virtual Reality Applications[END_REF] [START_REF] Trinkle | On Dynamic Multi-rigid-body Contact Problems with Coulomb Friction[END_REF]). The LCP relates contact forces and accelerations or velocities. For example, in a frictionless system, if f and a cp are two vectors in R m describing the normal contact forces and the relative normal accelerations at the m contact points, then there exists a m × m matrix A and a vector b in R m such as:

a cp = Af + b, a cp 0, f 0, a T cp f = 0 (1)
As a result, the number of degrees of freedom of the unconstrained system is not explicit. In other words, problem ( 1) is a contact-space formulation [START_REF] Ruspini | Collision/Contact Models for the Dynamic Simulation of Complex Environments[END_REF].

This paper uses Gauss' principle of least constraints to formulate both dynamics problems in the frictionless case in a motion-space. In the motion-space, an algorithm solving the dynamics problems is able to make explicit use of the number of dof in the simulation and avoids unnecessary computations. Note that some authors have presented formulations that explicitly contain the number of dof in the system. Lötstedt [START_REF] Lötstedt | Numerical simulation of time-dependent contact friction problems in rigid body mechanics[END_REF] uses a formulation closely related to Gauss' principle, but doesn't handle elastic collisions. Baraff[6] presents a linear-time algorithm for acyclic articuled bodies, but then uses a contact-space formulation [START_REF] Baraff | Fast Contact Force Computation for Nonpenetrating Rigid Bodies[END_REF] to handle unilateral contacts. Milenkovic [START_REF] Milenkovic | Optimization-Based Animation[END_REF], too, makes explicit use of the number of dof by formulating the problem as a quadratic programming problem, but requires many variables to enforce all the dynamics/collision conditions. This paper is organized as follows. Gauss' principle is recalled in Section 2. A motion-space formulation of the frictionless dynamics problems is derived from Gauss' principle in Section 3 to form similar minimization problems. Section 4 reduces the minimization problems to a well known nearestpoint problem (NPP) which will be our motion-based formulation. Section 5 compares both formulations from a theoretical and practical point of view. It shows that while the formulations are mathematically equivalent, they are not computationally equivalent: the motion-space formulation is better conditionned, is always sparse, requires less memory to store the data and avoids some unnecessary computations. An experimental comparison is made between two typical algorithms that solve the LCP problem and the NPP problem. A preliminary comparison suggests that, thanks to a sparser formulation, the algorithm operating in the motion-space (ie solving the NPP problem) is able to perform increasingly better than the algorithm operating in the contact-space, as the average number of contact points per object increases. Section 6 concludes.

Gauss' least constraints principle

Few references about applications of Gauss' principle of least constraints [START_REF] Gauss | Uber ein neues allgemeines Grundgesatz der Mechanik[END_REF] can be found. However, it has recently prompted a renewed interest [7][20]. Especially, Gauss' principle has been used in the special case of initially motionless objects [START_REF] Baraff | Impending Motion Direction of Contacting Rigid Bodies[END_REF] and, in robotics, to compute the dynamics of redundant manipulators [START_REF] Bruyninckx | Gauss' Principle and the Dynamics of Redundant and Constrained Manipulators[END_REF]. Udwadia [START_REF] Udwadia | Analytical Dynamics: a New Approach[END_REF] shows that Gauss' principle leads to a closed-form equation of motion when all the constraints are bilateral. An immediate advantage of Gauss' principle over the principle of virtual work, used in LCP methods, is that it allows to give a very intuitive formulation of the motion of a constrained system. Actually, it is so intuitive that it is often rediscovered and/or used without mentioning Gauss ([14]).

Though it was initially expressed for a set of point masses, it applies also for a frictionless system of rigid bodies subject to geometrical (unilateral or bilateral) constraints [START_REF] Baruh | Analytical Dynamics[END_REF][12], and can be simply expressed thanks to generalized accelerations and masses. Let's consider a contact group2 of n mobile objects. A rigid body i has only six degrees of freedom, and its acceleration is split into a translational term a i (G i ), which is the acceleration of the object's center of mass, and a rotational term α i . These two vectors are in R 3 . The accelerations of the n (potentially) mobile objects can be stacked in a single 6n-dimensional generalized acceleration vector a, while the masses and (time-dependant) inertia tensors can be stacked in a single 6n × 6n generalized mass matrix M. This matrix is block-diagonal and is symmetric positive definite (SPD). Now, let a u denote the (generalized) unconstrained acceleration of the contact group, that is, the accelerations the contact group would have were it not subject to geometrical constraints 3 . a u is in R 6n . Gauss' principle states that the generalized constrained acceleration a c minimizes the following scalar function of a over the set of possible accelerations:

G a (a) = 1 2 (a -a u ) T M(a -a u ) = 1 2 ||a -a u || 2 M (2)
The possible accelerations are the accelerations which are compatible with the current contact group's configuration.

Note that since M is SPD, ||.|| M is a well-defined noneuclidean norm. By analogy with the kinetic energy E = Figure 1: Gauss' principle allows to find very easily the particle's constrained acceleration. The particle's unconstrained acceleration a u is the gravity g. The possible accelerations are given by the non-penetration constraint due to the slope. The particle's constrained acceleration is the closest possible acceleration to its unconstrained acceleration.

set of possible accelerations 4 . Making implicit the fact that the distance is the kinetic one, Gauss' principle can be stated even more simply: at any moment, a contact group's constrained acceleration is the closest possible acceleration to its unconstrained acceleration.

In this formulation, the explicit unknowns are the objects' accelerations, and the contact forces are implicit: the problem is stated in the motion-space, and not in the contact-space, as in LCP methods [START_REF] Ruspini | Collision/Contact Models for the Dynamic Simulation of Complex Environments[END_REF]. Thus, the number of dof (6n) of the unconstrained contact group is explicit. Figure 1 shows an application of Gauss' principle for a particle laid on a slope and subject to gravity 5 .

Dynamics problems formulation

Constrained motion

The constrained motion problem for a contact group of n objects is a direct application of Gauss' principle, and all we have to do is express the set of possible accelerations. This set can be derived from the traditional contact model [START_REF] Baraff | Analytical Methods for Dynamic Simulation of Non-penetrating Rigid Bodies[END_REF][4] [START_REF] Ruspini | Collision/Contact Models for the Dynamic Simulation of Complex Environments[END_REF]. Let's denote two contacting objects by i and j. I is the contact point, n is the surface normal at I, directed from j to i. Depending on the object it belongs to, I is denoted by I i or I j . Using this notation, the non-penetration constraint on the contact points' accelerations is [START_REF] Baraff | Analytical Methods for Dynamic Simulation of Non-penetrating Rigid Bodies[END_REF]:

(a i (I i ) -a j (I j )).n + 2.(v i (I i ) -v j (I j )). dn dt 0 (3)
In a contact-space approach, this constraint would be used to form the matrix A and the vector b of the introduction, which relate contact forces and normal accelerations at the contact points. However, using Gauss' principle, we need to express this constraint on objects' accelerations. This is done simply: for any rigid object k, we have

a k (I k ) = a k (G k ) + α k ∧ G k I k + ω k ∧ (ω k ∧ G k I k )
, where ω k is the (known) rotational velocity of object k. Since v i (I i ), v j (I j ) and dn/dt are known [START_REF] Baraff | Analytical Methods for Dynamic Simulation of Non-penetrating Rigid Bodies[END_REF], inequation (3) is linear in the translational and rotational accelerations of the contacting objects. Stacking the m nonpenetration constraints (3) yields a single constraint on the contact group's acceleration Ja c, where J is the well-known m × 6n jacobian [START_REF] Ruspini | Collision/Contact Models for the Dynamic Simulation of Complex Environments[END_REF], and c is in R m . This general constraint defines the convex set of possible accelerations {a : Ja c}.

Finally, the constrained accelerations are:

a c = arg min 1 2 ||a -a u || 2 M : Ja c (4)
A common property of frictionless systems is immediately visible. Since a c minimizes a (non-euclidean) distance over a convex set, it is unique. Note that equation ( 4) yields the constrained accelerations for a contact group containing any number of objects subject to any number of (unilateral or bilateral 6 ) constraints.

Resolving collisions

Let us now derive a formulation of the collision resolution problem in the velocities space from Gauss' principle. Let v denote a generalized velocity of a contact group of n objects (v is in R 6n ), and let v -denote the (generalized) velocity that occurred immediately before the collision. The problem is to find v + , the (generalized) velocity that will occur immediately after the collision. To do so, we make two classical assumptions [START_REF] Ruspini | Collision/Contact Models for the Dynamic Simulation of Complex Environments[END_REF]: the first assumption is that the collision duration is infinitesimal [START_REF] Moore | Collision Detection and Response for Computer Animation[END_REF], and the second assumption is Poisson's hypothesis [START_REF] Mirtich | Impulse-based Simulation of Rigid Bodies[END_REF], which relates the objects' velocities at the contact points. As a result of the first assumption, we can consider that the object's positions during the collision, as well as the constraints acting on them, remain unchanged. Moreover, the exterior actions can be neglected compared to the intensity of the actions of the constraints. Accordingly, a u = 0. Let's assume now that the generalized acceleration is constant over the whole duration of the collision dt. This yields v +v -= adt. Since a u = 0, Gauss' principle allows to state that v + minimizes G v , where

G v (v) = 1 2 ||v -v -|| 2
M , over the velocities that can occur immediately after the collision. These possible separating velocities are found simply. In the case of (possibly) simultaneous collisions, Poisson's hypothesis yields the collision response constraint on the objects' velocities, for any of the m contact points (colliding or not)):

(v + i (I i ) -v + j (I j )).n -e(v - i (I i ) -v - j (I j )).n (5)
where e is the coefficient of restitution for the objects involved. Again, the velocities at the contact points depend on the objects' translational and rotational velocities. Consequently, inequation ( 5) is a linear function of the translational and rotational velocities of objects i and j. Stacking the m collision Figure 2: A particle has just collided a motionless object. The possible velocities are given by the collision response constraint, which depends on e, the coefficient of restitution. The particle's velocity immediately after the collision is the closest possible velocity to the particle's velocity immediately before the collision.

response constraints yields the set of possible (separating) velocities {v : Jv d}, where J is a m × 6n jacobian and d is in R m . Finally, the velocities occurring immediately after the collision are:

v + = arg min 1 2 ||v -v -|| 2 M : Jv d (6)
Once again, this result can be stated in a very elegant way: in a contact group, the velocities occurring immediately after a collision are the closest possible velocities to the velocities that occurred immediately before the collision. Figure 2 shows a collision resolution for a particle that has just collided a motionless object.

Solving the dynamics problems

Section 3 has reduced both dynamics problems to the same minimization problem:

x * = arg min 1 2 ||x -x u || 2 M : Jx c (7)
where x u , M, J and c are known. If the contact group contains n objects subject to m (unilateral) constraints, then x and x u are in R 6n , c is in R m , and J is in R m×6n . Since M is SPD, it can be factored as the product of two positive definite 6n × 6n matrices 7 :

M = Q T Q
It is now possible to make the contact forces (or impulses) visible, thanks to the lagrangian method. Hovever, we will end with a motion-based formulation. The lagrangian function associated to problem ( 7) is:

L(x, λ) = 1 2 ||x -x u || 2 M -λ T (Jx -c) (8)
The vector λ is in R m and represents contact forces or impulses, according to the dynamics problem being solved.

Since

∂L ∂x = 0 ⇔ x = M -1 J T λ + x u , (9)
the variable x can be eliminated (temporarily losing sight of the objects' motion). Thus, we must minimize:

f (λ) = 1 2 λ T JM -1 J T λ -λ T (c -Jx u ) (10)
under the constraint λ 0. Assuming the contact group's state is consistent, there exists a vector k such that Jk = c. We now use the factorization of M to retrieve a motion-based formulation. Let s = Q(kx u ) and J Q = JQ -1 . Minimizing ( 10) is equivalent to the following non-negative least-squares problem (NNLSP):

λ * = arg min 1 2 ||J T Q λ -s|| 2 : λ 0 (11)
Since J T Q λ and s are both in R 6n and since, from equation ( 9),

x = Q -1 J T Q λ + x u , this formulation is motion-based.
Geometrically, problem (11) consists in projecting s on the positive cone generated by the rows of 11) is thus a nearest-point problem (NPP).

J Q : C = {x : x = J T Q λ and λ 0}. Problem (

Comparing formulations

Mathematical equivalence

The equivalent contact-space formulation is obtained from problem (11). Indeed, the necessary and sufficient conditions of problem (11) are:

   JM -1 J T λ + Jx u -c 0, λ 0, (JM -1 J T λ + Jx u -c) T λ = 0. ( 12
)
This formulation is exactly8 the one given in Baraff[4] or Ruspini [START_REF] Ruspini | Collision/Contact Models for the Dynamic Simulation of Complex Environments[END_REF]. In this formulation, the number of dof in the contact group is implicit, since all vectors are in R m , and since the factorization of the operational inertia matrix JM -1 J T is hidden.

At this point, the reader may wonder why we did not derive problem (11) directly from the LCP formulation [START_REF] Lilov | Dynamic Analysis of Multi-rigid Body System Based on the Gauss Principle[END_REF]. After all, the only tricks involved are factoring the mass matrix M and noticing that Jx u -c is in the column space of JQ -1 . However, we believe that the insight into the intuitive underlying physics offered by Gauss' principle will help to understand why an algorithm solving problem (11) should be able to perform better than an algorithm solving problem [START_REF] Lilov | Dynamic Analysis of Multi-rigid Body System Based on the Gauss Principle[END_REF].

Computational difference

Whereas problems (11) and ( 12) are mathematically equivalent, they are not computationally equivalent for essentially four reasons:

• ill-conditionned matrix: the condition number of JM -1 J T is the square of that of J Q (see Gill [11], for example). As a result, problem ( 12) is much more illconditionned than problem (11), and is therefore much more sensitive to round-off errors.

• sparsity: Since M and Q are block-diagonal matrices, and since J is always sparse, the matrix J Q involved in problem ( 11) is always sparse as well. On the contrary, JM -1 J T may be dense [START_REF] Baraff | Linear-time Dynamics using Lagrange Multipliers[END_REF].

• memory: When the involved matrices are considered dense, it requires much more memory to store JM -1 J T (O(m 2 )) than to store J Q (O(nm)) as the number of contact points per object increases. Moreover, when the matrices are considered sparse, J Q always require O(m) only, while JM -1 J T may still be dense.

• unnecessary computations: an algorithm solving problem [START_REF] Lilov | Dynamic Analysis of Multi-rigid Body System Based on the Gauss Principle[END_REF] will have to enforce conditions on both contact forces (or impulses) λ and objects' accelerations (or velocities) at the contact points x cp . As a result, this algorithm will have to maintain the m coordinates of x cp while solving problem [START_REF] Lilov | Dynamic Analysis of Multi-rigid Body System Based on the Gauss Principle[END_REF]. However, the m coordinates of x cp are not independent, since the contact points belong to rigid bodies: these coordinates could be deduced from the objects' motions. Since these objects' motions are not readily available in a contact-space formulation, the algorithm will perform unnecessary computations. In the motion-space formulation, an algorithm is able to operate on the 6n truly independant motion coordinates only, and on the corresponding coefficients in J Q .

As a preliminary conclusion, let's state the difference between a contact-space formulation and a motion-space formulation more simply: in a contact-space approach, the contact forces are computed for themselves, and are then used to compute the object's motions. In a motion-space approach, the contact forces are computed along with the objects' motions 9 .

Experimental comparison

There are numerous ways to solve the nearest-point problem [START_REF] Lilov | Dynamic Analysis of Multi-rigid Body System Based on the Gauss Principle[END_REF]. However, its geometrical structure has led the optimization community to develop specific algorithms, generally split into two categories: combinatorial algorithms (active-set methods), and descent methods. Algorithms in the first category look for the solution by moving from face to face in the cone. Algorithms in the second category are interior-point methods or exterior-point methods [START_REF] Al-Sultan | Nearest Point Problems: Theory and Algorithms[END_REF]. For typical rigid body simulations, however, it is simpler to use active-set algorithms (as is the case in contact-space formulations: at least for frictionless systems, the LCP problems are solved by Lemke's algorithm or Dantzig's algorithm[2][4] [START_REF] Ruspini | Collision/Contact Models for the Dynamic Simulation of Complex Environments[END_REF][18] [START_REF] Trinkle | On Dynamic Multi-rigid-body Contact Problems with Coulomb Friction[END_REF]).

In an attempt to make an experimental comparison of both approaches, we chose to implement Baraff's well-known algorithm [START_REF] Baraff | Fast Contact Force Computation for Nonpenetrating Rigid Bodies[END_REF] to solve problem [START_REF] Lilov | Dynamic Analysis of Multi-rigid Body System Based on the Gauss Principle[END_REF]. This algorithm, in the frictionless case, is equivalent to Dantzig's algorithm for LCPs. For the NPP problem (11), we chose Wilhelmsen's algorithm [START_REF] Wilhelmsen | A Nearest Point Algorithm for Convex Polyhedral Cones and Applications to Positive Linear Approximations[END_REF] for several reasons. It is an active-set method, easy to implement and, most of all, is closely related to Dantzig's algorithm, making thus the comparison more pertinent. Actually, as most pivotal methods, both algorithms have an outer loop and an inner loop. In the inner loop, both algorithms need to solve linear systems involving submatrices of JM -1 J T (note that consequently, the assessment about ill-conditionning doesn't hold anymore. However, this allows to compare efficiency under equivalent robustness assumptions). The difference between the algorithms resides in the fact that Wilhelmsen's algorithm operates on J T Q λ and λ, while Dantzig's algorithm operates on x cp and λ. We used the n=2 n=7 n=12 n=17 n=22 p=5 0.60 0.50 0.51 0.54 0.52 p=15 0.85 1.08 same guidelines to implement both algorithms. The matrix J Q and the matrix JM -1 J T were treated as dense in a version of the algorithms, and as sparse in another. Cholesky factorizations were used to solve the linear systems in both cases. However, we did not implement an incremental factorization routine, for either algorithm, as suggested in [START_REF] Baraff | Fast Contact Force Computation for Nonpenetrating Rigid Bodies[END_REF]. Since preliminary tests did show that both algorithms performed approximately the same number of linear systems resolutions, no algorithm would have benefitted significantly more than the other. Note that the same tolerance value was used in both algorithms (ε = 10 -5 ).

Note that we are totally aware that, despite all our efforts to implement both algorithms with the same guidelines, it may still be argued that comparing execution times is not always pertinent. However, we are far less interested in the ratio of execution times than in the behavior of this ratio. For a given test, a random matrix J was computed in the following way. For any row, two integers where randomly chosen between 1 and n. These (possibly equal) integers where used to place two sets of six coefficients in a row, resulting in a typical jacobian matrix. The fact that the chosen integers could be equal enabled to simulate object/environment contacts. To obtain a vector c consistent with J, a random vector k was chosen in R 6n and c was set to Jk. The entries of the equivalent LCP problem were computed as in [START_REF] Lilov | Dynamic Analysis of Multi-rigid Body System Based on the Gauss Principle[END_REF], with M set to the 6n × 6n n=2 n=7 n=12 n=17 n=22 p=5 0.51 0.62 0.80 0.91 0.93 p=15 0.71 1. [START_REF] Trinkle | On Dynamic Multi-rigid-body Contact Problems with Coulomb Friction[END_REF]

r(n, p) = ∑ 50 i=1 t D i ∑ 50 i=1 t W i ( 13
)
Note that we chose n and p such as both problems could be stored in memory and didn't need disk access. The results are reported in Table 1 for the dense case (ie dense for both algorithms), and in Table 2 for the sparse case (ie sparse for both algorithms). Again, let's emphasize that we are not really interessed in the ratio of execution times for itself, but in its behavior. This behavior is demonstrated in Tables 1 and2: the algorithm operating in the motion-space takes (a better) advantage of sparsity to perform increasingly better than the algorithm operating in contact-space, as the number of contact points per object increases. Considering now the ratio in itself, and considering the fact that we used the same guidelines to implement both algorithms, we may (carefully) state that a motion-space algorithm performs better than a contact-space algorithm (at least for our implementation and for the tests we did). It should be clear that when the objects are simple and/or that there are few contacts per object, a contact-space approach will (not surprisingly) perform better. As the objects complexity increases, however, the motion-space formulation seems to be preferable.

Conclusion and results

Thanks to Gauss' principle of least constraints, the dynamics problems occuring in a frictionless rigid body simulation (the constrained motion problem and the collision resolution problem) have been formulated in the motion-space. While the resulting formulations are mathematically equivalent, they are not computationally equivalent. The main reasons for this is that the motion-space formulation is better conditionned, is always sparse, takes less memory, and is able to avoid some unnecessary computations. A preliminary experimental study suggests that an algorithm operating in the motion-space is able to take advantage of sparsity to perform increasingly better than a contact-space algorithm as the number of contact points per object increases 10 . As a conclusion, we note that the motion-space formulations given in this paper presently hold for frictionless systems only. Whereas frictionless simulations stand on their own and have practical applications (virtual prototyping, assembly tests and fitting operations for example), we believe that the encouraging results constitute a strong incentive to develop friction-handling algorithms derived from the motion-space approach. This problem is currently under research. Meanwhile, a complete frictionless rigid body engine, enabling second-order and first-order world 11 simulations, has been implemented and successfully tested with industrial (aeronautics) data in an immersive environment (Figure 3).

Figure 3 :

 3 Figure 3: Towards assembly tasks in an immersive environment (edited photograph of our simulator). Assembly tasks should benefit from an algorithm operating in a motion-space, as the increase in the objects complexity may result in many contact points.

Table 1 :

 1 Dense case: The ratio of execution times exhibits no significant behavior.

		1.23	1.47	1.63
	p=25 0.85 0.90 1.07	1.21	1.05
	p=35 0.94 0.93 1.31	1.15	1.01
	p=45 1.01 1.08	1.5	1.08	1.03

Table 2 :

 2 Sparse case: the motion-space algorithm takes advantage of spar-

	1.52	1.95	2.19
	p=25 0.70 1.04 1.60	1.98	1.90
	p=35 0.76 1.11 2.08	2.20	2.05
	p=45 0.78 1.34 2.44	2.43	2.20
	sity to perform increasingly better than the contact-space algo-
	rithm, as the number of contacts per object increases.
	identity matrix (which has obviously no impact on the com-
	parison). The two parameters of the tests were the number of
	objects n and the (average) number of unilateral constraints
	per object p. For a given pair (n, p), 50 execution times were
	obtained for Dantzig's and Wilhelmsen's algorithms: t D i and t W i , respectively, for 1 i 50. The ratio of average execu-
	tion times was then:

S. Redon and S. Coquillart are from INRIA-Rocquencourt -FRANCE.

A. Kheddar is from Université d'Evry CEMIF-SC -FRANCE

Contact author : stephane.redon@inria.fr[START_REF] Al-Sultan | Nearest Point Problems: Theory and Algorithms[END_REF] Of course, the collision detection is also slowing down the system.

v T Mv of the system, this norm is usually called kinetic norm. Thus, Gauss' principle amounts to minimize the kinetic distance between the generalized accelerations a and a u , over the 2 Throughout this paper, a contact group is a set of mobile objects. Two objects i and j are in the same contact group if and only if there exists a chain of contacting mobile objects from object i to object j. At any moment, any contact group is dynamically independent of the others. Therefore, in a rigid body simulation, the contact groups can be examined separately when solving the dynamics problems.

[START_REF] Baraff | Analytical Methods for Dynamic Simulation of Non-penetrating Rigid Bodies[END_REF] For example, the unconstrained acceleration of a cube laid on a table and subject to gravity g is precisely g.

Since G a and √ G a are minimized by the same a c .

For clarity, the examples given in this paper will concern particles. For isolated particles, the object space and the accelerations space can be superimposed, and the kinetic distance is proportional to the euclidean distance.

Since bilateral constraints can be expressed as pairs of unilateral constraints.

The objects' local inertia tensors are constant and can be factored offline. The matrix Q can thus be computed in O(n).

Note that for clarity, the formulations given in this paper are for 6-dof rigid bodies. However, Gauss' principle holds in reduced coordinates, and can be used along with the general contact model of Ruspini[START_REF] Ruspini | Collision/Contact Models for the Dynamic Simulation of Complex Environments[END_REF]. Besides, the mathematical equivalence given in this section is a proof of this, since all that is required is factoring M.

Since the objects' motions are directly related to J T Q λ.

Aknowledgements

The authors would like to thank Peter Spellucci for his precious help on quadratic programming. This study was funded by the French Ministry of Research through an AMX grant and the RNTL PERF-RV project. The Responsive Workbench TM was partially funded by the Regional Council of Ile-de-France.