est destinée au dépôt

Settled dust in preschools: characterization and genotoxicity of trace metals and polycyclic aromatic hydrocarbons

Type of gragh to be obtained

SETTLED

  Rebecca Castel, Virginie Tassistro, Stéphanie Lebarillier, Magalie Claeys-Bruno, Mathieu Izard, Franck Marot, Yves Noack, Thierry Orsiere, Laure Malleret To cite this version: Rebecca Castel, Virginie Tassistro, Stéphanie Lebarillier, Magalie Claeys-Bruno, Mathieu Izard, et al.. Settled dust in preschools: characterization and genotoxicity of trace metals and polycyclic aromatic hydrocarbons. Goldschmidt Conference 2021, Jul 2021, Lyon, France. . hal-03903491 Laboratoire Chimie Environnement, AMU, CNRS, ECCOREV FR, Marseille, France ; (b) IMBE, Equipe Biomarqueurs Environnement Santé, AMU, CNRS, IRD, AU, Marseille, France; (c) ATMOSUD, Marseille, France ; (d) ADEME, Angers, France; (d) CEREGE, AMU, CNRS, Collège de France, IRD, Aix-en-Provence, France PERSPECTIVES Children below 6 years old could be exposed to trace metals and PAH via ingestion of settled dust. Samplings of settled dust in schools of Bouches-du-Rhône (France) 2015 -2016 / 2020-2021 Mixture genotoxicity of 6 PAH and 6 metals of interest by using experimental designs

Figure 2 :

 2 Figure 2: concentrations of the 5 trace metals of interest in the different preschools, in winter and summer


Jacques Fourgeaud

Jean-François Magny

Sophie Couderc

Patricia Garcia

Anne-Marie Maillotte

Melinda Benard

Didier Pinquier

Philippe Minodier

Dominique Astruc

Hugues Patural

Melissa Ugolin

Sophie Parat

Bernard Guillois

Armelle Garenne

Tiffany Guilleminot

Marine Parodi

Laurence Bussières

Yves Ville

Marianne Leruez-Ville

cytomegalovirus DNA in blood and saliva over the first 24 months of life congenital infection: the French Cymepedia Cohort

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Cytomegalovirus infection is the most frequent congenital infection, with a birth prevalence of around 0.7% [START_REF] Leruez-Ville | Cytomegalovirus infection during pregnancy: state of the science[END_REF]. Congenital CMV is a frequent cause of sensorineural hearing loss and neurological disabilities, with about 20% of infected neonates developing long-term sequelae [START_REF] Leruez-Ville | Cytomegalovirus infection during pregnancy: state of the science[END_REF].

CMV PCR performed on a saliva sample is a reliable tool for diagnosing congenital infection at birth [START_REF] Rawlinson | Congenital cytomegalovirus infection in pregnancy and the neonate: consensus recommendations for prevention, diagnosis, and therapy[END_REF]. However, the evolution of CMV DNA excretion in saliva in the first two years of age and its association with prognosis is poorly known. CMV PCR in blood is not recommended for the neonatal diagnosis of congenital CMV because of its lack of sensitivity. . There are limited and conflicting data on whether CMV viral load in blood at birth or later reflects disease severity among symptomatically and asymptomatically infected infants and could be used as an indicator of prognosis.

The French multicenter Cymepedia cohort includes symptomatic and asymptomatic congenitally infected neonates. Within this cohort, samples of whole blood and saliva were prospectively collected at different times over the two first years of life. This constitutes a unique dataset of saliva and blood viral load in symptomatic and asymptomatic infants. The current study explored the kinetics of viral load in blood and saliva from birth to 2 years of age and its correlation with disease severity. The objective was to demonstrate the potential clinical utility of viral load determination in both compartments for the diagnosis and prognosis workup of infected infants.

Materials and methods

Population:

J o u r n a l P r e -p r o o f

The Cymepedia study included infected neonate/mother pairs in 11 French perinatal centers between 2013 and 2017. Neonates included in the study were diagnosed with congenital CMV either prenatally because of primary infection in the mother and/or compatible prenatal ultrasound features in the fetus or postnatally. The study was proposed to the parents of all children diagnosed with cCMV, and only around 5% of parents declined inclusion. The cohort was composed of a total of 256 neonates.

The Cymepedia study is registered on clinicaltrial.gov website under NCT01923636. All parents gave written consent for their children to participate in the study. The ethics committee at each participating site approved the study (2013-A00213-42).

Follow-up:

All infected children were followed with the same protocol, including visits at inclusion, 4, 12, 18, and 24 months of age. Clinical examination was standardized to assess motor, cognitive, speech, and psychological development according to age as previously described [START_REF] Leruez-Ville | Accuracy of prenatal ultrasound screening to identify fetuses infected by cytomegalovirus which will develop severe long-term sequelae[END_REF].

Audiological assessment and the presence of otitis media were recorded at each visit. A Brunet-Lezine test was done at months 12 and 24 to evaluate the early childhood psychomotor development scale covering four areas of neurodevelopment: movement and posture, coordination, language, and sociability (4). Auditory Brainstem Responses (ABRs) or audiology tests were performed depending on the child's age. Conductive SNHL (Sensorineural Hearing Loss) with the presence of otitis media with effusion was considered non-interpretable, and testing was repeated 4 to 6 months after resolution of otitis media. Transtympanic drains were placed when indicated. Hearing was considered to be normal if the child could hear stimuli between 0 and 20dB. SNHL was mild, moderate, severe, and profound for detecting sound within 21 to 30 dB, 31 to 60 dB, 61 to 90 dB, and ≥91 dB, respectively. Vestibular functions were assessed in children with SNHL and/or delayed walking as previously reported (3).

J o u r n a l P r e -p r o o f

Whole blood and saliva samples were collected at inclusion, second and third visits (month 4 and month 12) for the entire population. In 2015, we changed the protocol to collect saliva samples at the fourth and fifth visits (months 18 and 24). Therefore, only about half the population had saliva samples collected at these two last visits.

Classification of cases:

Children with any of the following sequelae were classified into the "sequelae" group: hearing loss (bilateral or unilateral), motor or cognitive impairment, epilepsy, vestibular disorders, visual impairment linked to retinitis.

Laboratory methods

Type of maternal infection and dating of a maternal primary infection were based on serological results as described elsewhere [START_REF] Leruez-Ville | Accuracy of prenatal ultrasound screening to identify fetuses infected by cytomegalovirus which will develop severe long-term sequelae[END_REF][START_REF] Leruez-Ville | Risk Factors for Congenital Cytomegalovirus Infection Following Primary and Nonprimary Maternal Infection: A Prospective Neonatal Screening Study Using Polymerase Chain Reaction in Saliva[END_REF]. Saliva samples were collected with flocked swabs and then discharged into transport medium (Copan, ESWABR1, Labelians, Nemours, France). DNA was extracted from 200 L of saliva or of whole blood sample on the EasyMag Extractor (BioMérieux, Marcy l'Etoile, France) and amplified using the real time PCR CMV R Gene assay (Argène BioMerieux). The limit of detection of the method is 2.5 log10 copies/mL in saliva and 2.6 IU/mL in whole blood; the limit of quantification is 2.7 log10 copies/mL in saliva and 2.8 IU/mL in whole blood.

Statistical analysis:

Because it was previously demonstrated that in utero valacyclovir treatment decreases viral load in fetal blood [START_REF] Jacquemard | Maternal administration of valaciclovir in symptomatic intrauterine cytomegalovirus infection[END_REF], CMV PCR results in blood collected at the first visit from neonates treated in utero by valacyclovir were excluded from the analysis. Moreover, blood and saliva samples from children treated by valganciclovir at the time of samples collection were excluded from the analysis.

J o u r n a l P r e -p r o o f

For comparison of viral loads, all positive viral loads under the limit of quantification of the technique (<2.7 log10 cp/mL or 2.8 log10 IU/mL) were assigned half the value of the limit of detection (1.35 log10 copies/mL or 1.4 log10 IU/mL).

Medians viral loads were compared between two groups (sequelae/ no sequelae groups and 1 st , 2 nd , 3 rd , 4 th and 5 th visits groups) using the Mann Whitney test, only two-tailed p values <0.05 were considered significant. Medians viral loads were compared between three or more groups using Kruskal-Wallis test; only p values <0.05 were considered significant.

The proportions between the 2 groups were compared by Fisher exact test; only two-sided p values <0.05 were considered as significant. The proportions between three or more groups were compared by Chi-square test; only p values <0.05 were considered as significant.

Sensitivity, specificity, negative predictive value (NPV), positive predictive value (PPV) were calculated. All analyses were conducted using GraphPad Prism 9 software (GraphPad Software, San Diego, California).

Results

Population

Among the 256 cases, the type of maternal infection was known for 246 cases: 202 were primary infections (99 in the 1 st trimester, 63 in the 2 nd trimester, 36 in the 3 rd trimester, and 4 undetermined); 44 were non-primary infections. For 10 cases, the type of maternal infection was unknown. According to the consensus classification (2), 157 neonates were asymptomatic, 98 were symptomatic at birth (including growth retardation and hearing loss), and for one neonate, the clinical status at birth was unknown.

Mothers of 52 neonates had been treated in utero with valacyclovir; 55 neonates were treated with valganciclovir postnatally for a median of 42 days (range: 10-203). Among the 256 infants, J o u r n a l P r e -p r o o f sequela. Among children with sequelae at month 24, 34 had received valganciclovir treatment in the neonatal period, and among children with no sequelae at month 24, 21 children had been treated in the neonatal period.

Kinetics of CMV DNA in saliva

Results of CMV PCR in infants treated with valganciclovir at the time of sample collection were not included in the analysis. Some infants were not sampled at all visits; however, saliva was collected in 97%, 90%, and 83% of the 256 included infants at the first, second, and third visit, respectively. Only 41% and 49% of the population was tested at fourth and fifth (see the material and methods section) Kinetics of CMV DNA in saliva are shown in Figure 1. Positive CMV DNA detection in saliva was 100% (240/240) at the second visit (median of 4.5 months). At the third visit, at a median of 12 months, 96% (199/208) of samples were positive. Then the proportion of positive CMV DNA detection decreased to 69% (72/105) at the fourth visit (median 19 months) and to 59% (75/126) at the last visit (median 24 months), respectively (Figure 1A). CMV DNA detection was positive in all the 113 saliva samples collected between 4-5, 58 of samples collected at 5-6, and 15 samples collected at 6-7 months of age; therefore, 100% of CMV PCR tests on saliva were positive up to 7 months. The first negative viral load in saliva was reported at day 338 (> 11 months), but due to the study design, only 13 tests were performed between 7 months and 11 months (Figure 1B). CMV shedding was intermittent in some infants: among the 9 children with a negative CMV PCR on saliva at month 12 visit, 5 were re-tested at month 18, and 3 had a positive saliva PCR. At month 18 visit, 33 infants had a negative PCR on saliva, 27 were retested at month 24, and 7 had a positive CMV PCR on saliva.

In positive samples, CMV DNA loads decreased progressively from birth to month 18. Viral load levels significantly decreased from inclusion (median 7.5 log10, IQR 6.7-8.1) to month 4 J o u r n a l P r e -p r o o f of age (median 7.1 log10, IQR 6.3-7.6) (p< 0.0001), from month 4 to month 12 (median 4.2 log10, IQR 3.6-5.1) (p<0.0001), from month 12 to month 18 (median 3.6 log10, IQR 2.7-4.2) (p<0.0001). Viral laod was not significantly different from month 18 to month 24 (median 3.2 log10, IQR 2.8-4.0) (p=0.3935).

Kinetics of CMV DNA in blood

Results of CMV PCR on blood samples collected at the first visit from neonates with in utero valacyclovir were excluded from the analysis. Results of CMV PCR on blood collected from infants being treated with valganciclovir at the time of collection were excluded from the analysis. Some infants were not sampled at all visits; however, a blood sample was collected in 97%, 90%, and 83% of the 256 included at the first, second, and third visit, respectively.

Kinetics of CMV DNA in blood are shown in Figure 2. The proportion of positive CMV PCR tests performed on whole blood decreased significantly from 92% (147/159) to 72% (175/240) and 27% (57/213) at inclusion, months 4 and 12, respectively. In positive samples, median CMV DNA loads decreased significantly from inclusion (median 3.9 log10, IQR 3.5-4.4) to month 4 (median 3.4 log10, IQR 2.9-3.9) (p<0.0001) and from month 4 to month 12 (median 1.4 log10, IQR 1.4-3.1) (p<0.0001).

Comparison of duration and the level of CMV by specimen and patient characteristics

There was no significant difference in positivity rate and viral load level in saliva between children with or without sequelae at any visits (Figure 3; available at www.jpeds.com).

All children with sequelae had a positive PCR in blood with a viral load above 3 log10 IU/mL at inclusion (Figure 4). The median viral load at inclusion (median 13 days) and at the second visit (median 4.5 months) was significantly higher in the group of children with sequelae than in the group of children without sequelae (p=0.0013 and p<0.0001, respectively). At the third J o u r n a l P r e -p r o o f visit (median 12 months), having a positive CMV PCR in blood was significantly more frequent in children with sequelae than in children without sequelae (p=0.0029).

The sensitivity, specificity, PPV, NPV for long-term sequelae of a CMV PCR in blood >3.0 log10 IU/mL was 100%, 16%, 18% and 100% respectively. The sensitivity, specificity, PPV, NPV for long-term sequelae of a CMV PCR in blood >3.5 log10 IU/mL was 95%, 33%, 21% and 97% respectively. The sensitivity, specificity, PPV, NPV for long-term sequelae of a CMV PCR in blood >4 log10 IU/ml was 68%, 60%, 24% and 91% respectively.

In the first month of life (inclusion visit), CMV DNA load in saliva was significantly lower in neonates infected after maternal primary infection in the 3 rd trimester than in neonates infected after a maternal primary infection in the 1 st or 2 nd trimesters (Figure 5A). Among children infected after a maternal primary infection in the 3 rd trimester, viral loads in saliva significantly increased when the time interval between the date of the maternal infection and birth increased.

Median viral load increased from 4.6 log10 (IQR 1.4-4.7) to 6.7 log10 copies/mL (IQR 5.2-7.7) to reach a plateau at 8.0 log10 (IQR 7.5-8.4,) for an interval between the date of the maternal primary infection and birth of 3 to 4 weeks, 5 to 7 weeks and 8 to 12 weeks respectively (p<0.0001; p=0,0059; p=0.0045) (Figure 5B).

From the second visit (at a median of 4.5 months) onward to the last visit (median 24 months), the proportion of positive saliva samples and the median viral load in positive samples were not significantly different between children infected after primary maternal infection in the first, second and third trimester (Figure 6; available at www.jpeds.com).

Only two neonates (2/86, 2%) infected after a maternal primary infection in the first or second trimester had a viral load in saliva below 5.0 log10 copies/ml (Figure 5B). Among these 2 cases, 1 had a prenatal diagnosis with a negative CMV PCR in amniotic fluid sampled at 22 weeks suggesting a late passage of the virus that could explain the low viral load at birth [START_REF] Bilavsky | Clinical Implications for Children Born With Congenital Cytomegalovirus Infection Following a Negative J o u r n a l P r e -p r o o f Amniocentesis[END_REF].

Unfortunately, prenatal diagnosis was not done in the other case, and the time of CMV J o u r n a l P r e -p r o o f transplacental passage was not documented. Those 2 cases had a good outcome with no sequelae at 2 years of age.

The proportion of positive CMV PCR in blood and the level of median viral loads in positive samples were not significantly different between children infected after a maternal infection in the first, second and third trimester (Figure 7; available at www.jpeds.com).

At the first visit, newborns treated with valganciclovir had lower saliva viral loads than patients without treatment (Figure 8; available at www.jpeds.com). At the second visit (age 4 months), although viral load levels in positive samples were the same in the 3 groups, we observed fewer positive saliva PCR (41% vs. 100%) in infants who received or had received valganciclovir.

From the 3rd visit onwards, there was no difference in saliva PCR positivity rate or viral load level. No difference was observed in viral blood load levels in infants treated with valganciclovir treatment (Figure 9A; onlineavailable at www.jpeds.comhowever, treated infants were more likely to have a positive CMV PCR in blood at month 12 possibly reflecting the rebound in viral load after the end of therapy as reported by Kimberlin et al [START_REF] Kimberlin | Valganciclovir for symptomatic congenital cytomegalovirus disease[END_REF].

In utero valacyclovir treatment had no effect on both positivity rate and viral load level in saliva samples at first visit (Figure 8). However, as expected from previous data (6) in utero valacyclovir treatment was associated with significantly decreased viral load blood level (3.6 vs 4 log IU/mL; p=0.0464) in the first 7 days of life (Figure 9B).

Discussion

This study reports new longitudinal data on saliva and blood viral loads within a large prospective cohort of symptomatic and asymptomatic neonates with congenital CMV infection. studies based on viral culture reported a positive CMV culture in 97% of urine samples and in 87% of oral samples collected in the first year of life [START_REF] Pass | Specific cell-mediated immunity and the natural history of congenital infection with cytomegalovirus[END_REF]. Longitudinal data on CMV DNA excretion quantified by PCR in the urine and saliva of children with cCMV are scarce. One J o u r n a l P r e -p r o o f study reported in 33 infants, 100% of CMV DNA excretion in the urine at 3 and 18 months and 100% and 47% at 3 and 18 months respectively in the saliva [START_REF] Puhakka | Viral shedding, and distribution of cytomegalovirus glycoprotein H (UL75), glycoprotein B (UL55), and glycoprotein N (UL73) genotypes in congenital cytomegalovirus infection[END_REF]. Another study reported CMV DNA excretion in the urine in 85% and 75% of 33 infants at months 12 and 24 respectively [START_REF] Forner | High Cytomegalovirus (CMV) DNAemia Predicts CMV Sequelae in Asymptomatic Congenitally Infected Newborns Born to Women With Primary Infection During Pregnancy[END_REF]. In the current study, we observed a progressive decrease in saliva viral load level from 7.5 log10 copies/mL at birth to 3.3 log10 copies/mL at month 24. No correlation was found between the proportion of positive CMV PCR and the level of viral load in saliva from birth to 2 years of age and the presence of long-term sequelae. CMV DNA was detected in 100% of saliva samples collected up to 6 months. This has value in clinical practice for the retrospective diagnosis of congenital CMV because a repeatedly negative PCR in saliva in the first 6 months of age likely excludes congenital CMV infection as in our cohort, which was predominantely due to primary infection during pregnancy, 100% of salivary samples were positive in the first 6 months.

CMV PCR in blood might be negative although the neonate is infected and shows positive CMV PCR in saliva. A retrospective study in the USA reported 8% of negative PCR in 74 infected children younger than 2 months [START_REF] Ross | Cytomegalovirus blood viral load and hearing loss in young children with congenital infection[END_REF]. In our prospective study, using CMV PCR in whole blood, the proportion of negative PCR in blood in congenitally infected children less than 1 month of age was 7% (12/159). The predictive value of neonatal blood viral load for long-term sequelae is still a matter of debate. A link between neonatal blood viral load and the risk of long-term sequelae was reported in two small retrospective studies. Lanari et al [START_REF] Lanari | Neonatal cytomegalovirus blood load and risk of sequelae in symptomatic and asymptomatic congenitally infected newborns[END_REF] were the first to report a 70% risk of sequelae in newborns with a viral load higher than 10,000 copies per 10 5 polymorphonuclear leukocytes. Forner et al [START_REF] Forner | High Cytomegalovirus (CMV) DNAemia Predicts CMV Sequelae in Asymptomatic Congenitally Infected Newborns Born to Women With Primary Infection During Pregnancy[END_REF] reported a risk of sequelae over 50% when CMV DNAemia at birth was 12,000 copies/mL. Conversely, Marsico et al [START_REF] Marsico | Blood Viral Load in Symptomatic Congenital Cytomegalovirus Infection[END_REF] failed to find a clinically relevant neonatal viral load threshold predictive of long-term sequelae in a cohort of 120 symptomatic infants. In our large prospective study of 256 infected neonates show that a high viral blood at birth is not a predictor of long-term sequelae in a population J o u r n a l P r e -p r o o f including both symptomatic and asymptomatic neonates. Indeed, although median blood viral loads were significantly higher at inclusion and month 4 in children with sequelae than in children with no sequelae, the viral load levels were largely overlapping between the 2 groups.

A clinically relevant threshold could not be found; therefore, high neonatal blood viral load cannot identify, among infected neonates symptomatic or asymptomatic, those with a high risk of long-term sequelae who could potentially benefit from neonatal treatment. Two studies suggested that a low blood viral load (<3 log10 copies/mL and <3.5 log10 genomes/mL respectively) could be associated with a good outcome [START_REF] Marsico | Blood Viral Load in Symptomatic Congenital Cytomegalovirus Infection[END_REF][START_REF] Boppana | Congenital cytomegalovirus infection: association between virus burden in infancy and J o u r n a l P r e -p r o o f hearing loss[END_REF]. In our large prospective study, a neonatal blood viral load < 3 log10 IU/mL had a 100% negative predictive value for long-term sequelae. Caution is required in generalizing these results to other population and because interassay result comparison remains an issue even with standardized CMV PCR assays expressed in IU/mL [START_REF] Preiksaitis | Are We There Yet? Impact of the First International Standard for Cytomegalovirus DNA on the Harmonization of Results Reported on Plasma Samples[END_REF].

We could not identify any difference in terms of viral load level and the duration of detection in blood and saliva according to the time and type of maternal infection. Except that viral loads in saliva at birth were significantly lower in women infected after a primary infection during the third trimester. This could be explained by the dynamic of CMV fetal replication after maternal primary infection. Our data show that CMV load in saliva is already detectable at a median of 4.6 logs by 3 weeks after primary maternal infection, increased to a median of 6.5 logs by 5 weeks and reache a plateau 8 weeks after primary maternal infection. Earlier studies reported a similar pattern of CMV DNA kinetics in amniotic fluid after a primary maternal infection, with the first detection of a low level of CMV DNA at 3 to 4 weeks after the primary maternal infection, increasing steadily until it reaches a plateau around 10 to 12 weeks after maternal infection [START_REF] Gouarin | Realtime PCR quantification of human cytomegalovirus DNA in amniotic fluid samples from mothers with primary infection[END_REF]18).

Our study has some limitations. The population of the study was not subjected to a systematic screening at birth and was enriched for primary infection during pregnancy which may affect J o u r n a l P r e -p r o o f generalizability. However, the population was large enough to compare children with and without sequelae. Among the 45 children with sequelae at 24 months, 34 had received neonatal treatment, which could significantly impact the long-term outcome [START_REF] Kimberlin | Valganciclovir for symptomatic congenital cytomegalovirus disease[END_REF]. Because valacyclovir treatment decreases blood viral load [START_REF] Jacquemard | Maternal administration of valaciclovir in symptomatic intrauterine cytomegalovirus infection[END_REF], we chose to exclude baseline neonatal blood viral load data for 51 neonates (including 11 cases with sequelae at 24 months) treated with valacyclovir in utero. Moreover, some children were already treated with valganciclovir at the time of inclusion, and baseline viral load in blood and saliva could not be analyzed for these 20 cases, including 11 children with sequelae at month 24. Finally, because saliva samples were not collected repeatedly in the first 6 months but only at 2 times for each infant, potential intermittency of shedding could not be completely eliminated although the high viral loads detected in saliva in this period suggest it is unlikely.

The strength of our study is its large population of children included prospectively, with a limited number of children lost to followup (10%) at 24 months of age. Moreover, the blood and saliva collection were both collected in 97%, 90%, and 83% of the 256 included children tested at baseline, second and third visits.

Our study demonstrates potential clinical value of performing saliva CMV PCR to 6 months of age in the assessment of infants not screened at birth and presenting with symptoms suggestive of congenital CMV infection. This study suggested that negative saliva collected in the first 6 months of life had a 100% negative predictive value for congenital infection, however further studies are needed to exclude intermittency of viral shedding and to confirm this finding for congenital infections following non-primary infection. Our study also demonstrated that a neonatal blood viral load <3.0 log10 IU/mL had a 100% negative predictive value for the occurrence of long-term sequelae. This threshold expressed in IU, if confirmed in other settings J o u r n a l P r e -p r o o f of congenital CMV infection, potentially could be useful for the management of infected neonates as well as for parents' counseling.

J o u r n a l P r e -p r o o f

Figures' legends

1 A:Figure 2 :Figure 3 :Figure 4 :Figure 5 :Figure 6 :Figure 7 :

 1234567 Figure 1

Figure 8 :

 8 Figure 8: Proportion of positive CMV PCR in saliva and levels of CMV DNA loads in positive

Figure 9 :

 9 Figure 9: Proportion of positive CMV PCR in blood and levels of CMV DNA loads in positive

Acknowledgments:

We thank all women and parents who participated in the trial. We also thank URC-CIC Paris Descartes (Laurence Lecomte, Guillaume Masson, Eric Dufour, Myriam Virlouvet, Cindy Parent) for the implementation, monitoring, and data management of the study. The sponsor was Assistance Publique_Hôpitaux de Paris (Délégation à la recherche Clinique et l'Innovation). The study was funded by a grant from programme Hospitalier de Recherche Clinique PHRC (Ministère de la Santé N° 2013-A00213-42).

J o u r n a l P r e -p r o o f

support from BioMérieux, non-financial support from Abbott, nonfinancial support from Diasorin outside the submitted work. YV reports non-financial support from GE Medical, non-financial support from Ferring SAS, non-financial support from Siemens Health care outside the submitted work. JFM reports personal fees from ABBVIE outside the submitted work.


Stéphane Redon
email: stephane.redon@inria.fr

Abderrahmane Kheddar
email: kheddar@iup.univ-evry.fr

Sabine Coquillart
email: sabine.coquillart]@inria.fr

Fast Continuous Collision Detection between Rigid Bodies

Keywords: Descriptors (according to ACM CCS): I, 3, 7 [Computer Graphics]: Animation -Virtual Reality

This paper introduces a fast continuous collision detection technique for polyhedral rigid bodies. As opposed to most collision detection techniques, the computation of the first contact time between two objects is inherently part

of the algorithm. The method can thus robustly prevent objects interpenetrations or collisions misses, even when objects are thin or have large velocities. The method is valid for general objects (polygon soups), handles multiple moving objects and acyclic articulated bodies, and is efficient in low and high coherency situations. Moreover, the method can be used to speed up existent continuous collision detection methods for parametric or implicit rigid surfaces. The collision detection algorithms have been successfully coupled to a real-time dynamics simulator. Various experiments are conducted that show the method's ability to produce high-quality interaction (precise objects positioning for example) between models up to tens of thousands of triangles, which couldn't have been performed with previous continuous methods.

Introduction

Collision detection (CD) is still a fundamental problem in numerous domains. Typical examples are computer graphics (physically-based modeling, animation), robotics (motion planning, collision avoidance), industrial applications (virtual prototyping, assembly tests) and video games. Moreover, haptics research has created the need of algorithms able to achieve kilohertz rates. Collision detection methods are usually split into two categories:

Discrete methods Most previous collision detection methods are discrete: they sample the objects motions and detect objects interpenetrations (see for example 1, 2, 6, 10, 11, 12, 13, 17, 25, 29 ). As a result, these methods may miss collisions (tunneling effect). While an adaptative time-step and predictive methods can be used to correct this problem in offline applications, this may not be suitable in interactive applications when a relatively high and constant frame-rate is required. Moreover, discrete collision detection requires backtracking methods to compute the first contact time, which is necessary in constraintbased analytical dynamics simulations. Depending on the object complexity, however, the computational cost of backtracking may be unpredictably large, mainly because estimating the penetration depth is a difficult problem, for example when many triangles have penetrated or if the object is concave or non-connex. Such typical problems are encountered in the interaction technique described in Snyder [START_REF] Snyder | An interactive tool for placing curved surfaces without interpenetration[END_REF] . In haptics, the penetration problem is a major cause of instability [START_REF] Gregory | Six degree-of-freedom haptic display of polygonal models[END_REF] . Continuous methods As opposed to these methods, continuous methods compute the first time of contact during the collision detection. This computation is inherently part of the algorithm. While more suitable to robust interactive dynamics simulations (to guarantee collision-free motions), continuous methods are usually slower than discrete methods, and are often abandonned for discrete ones [START_REF] Snyder | An interactive tool for placing curved surfaces without interpenetration[END_REF] .

This paper contributes to the field by introducing a fast continuous method, able to compute collision times between rigid polyhedral objects composed of tens of thousands of triangles at interactive rates (Figure 1). To our knowledge (see Section 2), this is not possible for previous continuous methods. The collision detection algorithms require no particular topology (objects can be polygon soups), can handle multiple moving objects and are efficient for slow and fast objects. Moreover, the method handles acyclic articulated bodies and can be used to speed up previous continuous collision detection methods for parametric or implicit rigid surfaces.

The algorithms described in this paper rely upon the effective integration of interval arithmetic (IA) and hierarchies of oriented bounding boxes (OBBs). Both approaches benefit from each other. Interval arithmetic is used to robustly compute collision times between objects features (vertices, edges and faces), and to derive a conservative continuous overlap test between moving OBBs from a well-known discrete overlap test. Conversely, the bounding boxes help to cull many irrelevant elementary tests (edge/edge, vertex/face and face/vertex tests), which made previous interval methods unpractical for complex polyhedral objects.

The next section describes previous work on continuous methods. Section 3 provides an overview of the method. It details the fixed in-between rigid motion assumption, recalls basic principles of interval arithmetic and of bounding volume hierarchies. Section 4 introduces the continuous overlap test between moving OBBs and presents the elementary CD tests (edge/edge, vertex/face and face/vertex). Section 5 briefly explains how our method may be used to speed up CD methods for parametric or implicit rigid surfaces. Section 6 describes several optimizations. The algorithms described in this paper have been coupled to dynamics algorithms [START_REF] Redon | Gauss' least constraints principle and rigid body simulations[END_REF] . Section 7 presents various experiments conducted to test the interactive simulator. Finally, Section 8 concludes and gives future research directions.

Previous work

There are relatively few continuous collision detection (CD) techniques. Canny 5 uses a parameterization of the objects trajectories based on quaternions and computes the collision time by solving low-order polynomials, but the algorithm's high complexity doesn't allow real-time interaction between large models. Redon et al. [START_REF] Redon | An Algebraic Solution to the Problem of Collision Detection for Rigid Polyhedral Objects[END_REF] use screwings to parameterize the trajectories of rigid polyhedral bodies and obtain a motion similar to the one in Canny 5 . The approach is extended to hierarchies of bounding spheres in Redon et al. [START_REF] Redon | CONTACT: arbitrary in-between motions for continuous collision detection[END_REF] to continuously detect collisions between rigid polyhedral bodies in real-time. However, since spheres don't fit objects well, the approach can only handle moderately complex objects (a few thousands of triangles). Moreover, the algorithm handles only one mobile object. It is noted in [START_REF] Redon | CONTACT: arbitrary in-between motions for continuous collision detection[END_REF] , though, that using arbitrary in-between rigid motions over successions of small time intervals allows realistic real-time dynamics simulations.

Cameron 4 introduces spatio-temporal extrusion to determine contact between moving CSG objects. However, due to the high computational cost of the extrusion operation, the object motions are piecewise translational.

Von Herzen et al. [START_REF] Von Herzen | Geometric Collisions for Time-Dependent Parametric Surfaces[END_REF] use Lipschitz bounds and binary subdivision to find the first contact time between timedependent parametric surfaces. Hierarchies of bounding spheres and axis-aligned bounding boxes are computed during collision detection to speed up the method. Duff 8 uses interval arithmetic and binary subdivision to detect collisions between boolean combinations of implicit surfaces. Snyder et al. 28 use interval arithmetic and interval Newton methods to significantly speed up these approaches, and use a simple culling test based on bounding spheres to adress the n-body problem. While the algorithm has many interesting features and is pratical for computer graphics animations, it is not efficient enough to handle real-time interaction, even for rigid bodies [START_REF] Snyder | An interactive tool for placing curved surfaces without interpenetration[END_REF] . General polyhedral objects may be considered as unions of parametric surfaces. However, none of interval-based methods able to handle parametric surfaces ( [START_REF] Von Herzen | Geometric Collisions for Time-Dependent Parametric Surfaces[END_REF]28 ) use hierarchies of bounding volumes to speed up the detection between unions of objects. Consequently, detecting a collision between two complex polyhedral objects is turned into an artificial and unpractical n-body problem (for example, see the multiple elements algorithm in Snyder et al. 28 ).

Mirtich [START_REF] Mirtich | Impulse-based dynamic simulation of rigid body systems[END_REF] uses physical laws to bound the times of impact, and is able to perform collision checks only when necessary. However, the lower bounds may be difficult to obtain for multibodies or complex motions, and the resultingly varying timestep may not be suited for interactive applications.

Note that some methods perform discrete CD on bounding volume hierarchies and continuous CD between polyhedral primitives [START_REF] Lennerz | A Framework for Collision Detection and Response[END_REF] . Some other methods perform pseudocontinuous CD by bounding at runtime the initial and final object's (or bounding-volume's) positions [START_REF] Eckstein | Dynamic collision detection in virtual reality applications[END_REF] . However, these methods don't ensure that the whole object trajectory is bounded and thus may miss collisions. The only case when bounding the initial and final object positions is valid is the much simpler one of a single moving vertex. In this case, some methods achieve continuous collision detection at haptic rates [START_REF] Gregory | Fast and accurate collision detection for haptic interaction using a three degree-of-freedom force-feedback device[END_REF] .

Overview

Arbitrary in-between rigid motions

As in Redon et al. [START_REF] Redon | CONTACT: arbitrary in-between motions for continuous collision detection[END_REF] , this paper uses arbitrary in-between rigid motions. Successive objects' positions, determined at fixed instants by the dynamics simulator or by the user interface, are interpolated with an arbitrarily fixed rigid motion. Arbitrary meaning that the in-between motion must be continuous and rigid, in order to get a truly continuous collision detection method. Precisely, interpolations are performed between the objects' positions at time t i and the intentional objects' positions at time t i+1 . Typically, t 0 , t 1 , . . . correspond to the display times. Thus, the interpolations occur between frames. Provided that the simulation timestep is small, the difference between the actual objects' motions and the interpolated ones is negligeable. Note that this approximation principle is similar to the one used in dynamics simulations: the dynamics equations are discretized and loworder approximations are used to move the objects between the instants chosen by the simulator.

The in-between rigid motion used in this paper, though, differs from the one in [START_REF] Redon | CONTACT: arbitrary in-between motions for continuous collision detection[END_REF] . The arbitrary in-between motion used in [START_REF] Redon | CONTACT: arbitrary in-between motions for continuous collision detection[END_REF] is designed to obtain an algebraic collision test, for which there is a closed-form contact time, and thus is nonnatural in dynamics simulations. This isn't required in the present paper since interval arithmetic is used to find roots of functions. Consequently, the in-between rigid motion we use is simply a continuous screwing, with constant rotational and translational velocities.

For clarity, let us assume that the current time interval is [0, 1] (between two frames for example). The screwingbased in-between motion in a reference frame R 0 is a 4 × 4 homogeneous matrix:

S(t) = P -1 V(t)P t ∈ [0, 1] (1)
where V(t) is a z-axis screwing, and P is the transformation matrix from R 0 to the screwing local frame. If ω and s are respectively the total amount of rotation and translation during the current time interval, then:

V(t) =     cos(ω.t) -sin(ω.t) 0 0 sin(ω.t) cos(ω.t) 0 0 0 0 1 s.t 0 0 0 1     (2)
for t ∈ [0, 1]. For acyclic articuled bodies, these screwingbased motions can be composed, starting from the root of the graph describing the body.

Note that other in-between motions can be arbitrarily chosen, provided they are continuous and rigid. For example, one solution consists in linearly interpolating the six independent parameters describing the object's position and orientation between successive frames.

Interval arithmetic

A good introduction to interval arithmetic for computer graphics can be found in Snyder 26 . The use of interval arithmetic to detect collisions between parametric or implicit surfaces is explored in Von Herzen et al., Duff 8 , and Snyder et al. 28 .

Briefly, interval arithmetic consists in computing with intervals instead of numbers. The definition of a real interval [a, b] is:

I = [a, b] = {x ∈ IR, a x b}
This can be generalized to vector-valued intervals:

In = [a 1 , b 1 ] × ... × [a 1 , b 1 ] = x = (x 1 ,...,xn) ∈ IR n , a i x i b i ∀i, 1 i n
The set of intervals of real numbers is denoted by IIR, while the set of vector-valued intervals is denoted by IIR n . Elementary operations on real numbers can be transposed to intervals:

[a, b] + [c, d] = [a + c, b + d] [a, b] -[c, d] = [a -c, b -d] [a, b] × [c, d] = [min(ac, ad, bc, bd), max(ac, ad, bc, bd)] 1/ [a, b] = [1/b, 1/a] if a > 0 or b < 0 [a, b] / [c, d] = [a, b] × (1/ [c, d])
(3)

For vector-valued intervals in IIR n , the operations are performed for each coordinate.

In the algorithms described in this paper, intervals are used to bound function ranges on intervals. Precisely, for any given function f : IR → IR, an inclusion function f :IIR →IIR is associated to f , such as:

x ∈ I ⇒ f (x) ∈ f (I) (4)
for any interval I. The ideal inclusion functions are those which exactly bound the function range, whatever the interval I.

From equations ( 1) and (2), the only inclusion functions required are those of the sine and cosine functions. Moreover, in the continuous overlap test derived in Section 4, one more inclusion function is required for the abs function (abs : x → |x|). For these functions, inclusion functions are easily computed 26 . Then, appropriate elementary operations (equation (3)) are recursively applied to compute inclusion functions for the coordinates of a vertex or a vector. The coordinates of a mobile vertex in frame R 0 are:

x G (t) = P -1 V(t)PPoxo (5)
where xo are the vertex coordinates in the object frame, and Po is the transformation matrix from the local object frame to the reference frame R 0 . Consequently, the coordinates inclusion functions are:

xG (t) = P -1 Ṽ(t)PPoxo (6)
where operations are performed on intervals, according to equation (3).

The interest of inclusion functions is that they provide a simple way to robustly compute the roots of a function f : I → IR. The simplest of these methods is the recursive binary subdivision method. Let's assume that an inclusion function f is available. Then f (I) = [a, b] is computed. If a > 0 or b < 0, then there can't be any root in I. Otherwise, there may be a root (may only since f (I) may not fit exactly f 's range over I, and/or f may not be continuous). In this case, interval I is cut into two equal intervals [a, m] and [m, b], where m = 1/2(a + b), and the computations are now performed on smaller intervals. This process is recursively performed until an interval width is smaller than a pre-determined threshold (the user-defined precision of the collision detection, see Section 4). In this case, the algorithm declares that a root has been found. It can be shown that if f is continuous on interval I, then the algorithm can't miss any root.

Note, however, that if f (x) = 0 over a non-empty interval, then the method returns only a finite number of intervals containing all the roots. The number of intervals returned depend on the pre-determined threshold. In Snyder et al. 28 , multidimensional interval-based root-finding is performed to detect collision between time-varying parametric or implicit surfaces.

Bounding volume hierarchies

Using bounding volume hierarchies (BVH) is a common strategy in collision detection and other domains (ray-tracing for example), which is naturally related to interval-based root-finding. Briefly, overlap tests between bounding volumes are used to cull many irrelevant elementary tests between objects parts. Let's assume, for example, that each of the two objects currently processed by the CD algorithm is bounded by a sphere. If the spheres don't overlap, then there can't be any collision between the objects. If the spheres do overlap, however, then there may be a collision between the objects (may only since the spheres probably don't exactly fit the objects). In this case, the spheres are replaced by unions of smaller spheres and overlap tests between spheres are recursively performed. When spheres sizes are smaller than a pre-determined threshold, exact tests are performed between the object geometries (for example, triangle/triangle collision tests, in the case of triangle soups). For rigid objects, the hierarchies of bounding volumes are usually computed offline. Typical bounding volumes are spheres [START_REF] Hubbard | Collision detection for interactive graphics applications[END_REF] , axis-aligned bounding boxes, oriented bounding boxes [START_REF] Baraff | Curved surfaces and coherence for nonpenetrating rigid body simulation[END_REF]13 , k-dops 17 and spherical shells [START_REF] Krishnan | Spherical Shell: A Higher Order Bounding Volume for Fast Proximity Queries[END_REF] .

We choose to use OBB hierarchies because of their performance in a wide range of applications, especially closeproximity situations. The hierarchies are binary trees built in a classical way [START_REF] Baraff | Curved surfaces and coherence for nonpenetrating rigid body simulation[END_REF]13 . We noticed that the tightest hierarchies were usually obtained with the min-max method [START_REF] Baraff | Curved surfaces and coherence for nonpenetrating rigid body simulation[END_REF] .

Continuous collision detection

This section describes the integrated collision detection algorithms: a well-known discrete overlap test between OBBs is extended to the continuous case, and the continuous CD functions for polyhedral primitives (vertices, edges and faces) are detailed. The precision problem, which is naturally handled by interval arithmetic, is also adressed.

Collision detection between OBBs

Discrete overlap test

The most efficient discrete overlap test between two static OBBs is probably the one described by Gottschalk et al. 13 , which relies upon the separating axis theorem.

Let us assume that the first OBB is described by three axes e 1 , e 2 and e 3 , a center T A , and its half-sizes along its axes a 1 , a 2 and a 3 . In the same way, the second OBB is described by its axes f 1 , f 2 and f 3 , its center T B , and its half-sizes along its axes b 1 , b 2 and b 3 . The separating axis theorem states that two static OBBs overlap if and only if all of fifteen separating axis tests fail. A separating test is simple: the axis a separates the OBBs if and only if

|a • T A T B | > 3 ∑ i=1 a i |a • e i | + 3 ∑ i=1 b i |a • f i | (7)
The fifteen sufficient axes are deduced from the OBBs axes: or by using more sophisticated methods to reduce the interval width, like Newton interval methods 26,28 . In order to avoid automatic subdivisions or computationally intensive methods, we propose as a second step a simple subdivision test. This test is an heuristic similar in spirit to Newton interval methods, since it depends on the OBBs velocities, but is far cheaper to compute. Subdivision test Generally, an axis separating the OBBs at a given instant won't be separating during the whole time interval when objects move too fast relatively to their sizes. This is exactly what the subdivision test adresses: briefly, the OBBs are projected on their relative velocity directions. First, the relative velocity of the OBBs centers at the beginning of the time interval are computed. This amounts to consider that the second OBB is static. Assuming T A is expressed in the reference frame R 0 , then its velocity can be derived from equation (5):

a ∈ {e i , f j , e i × f j , 1 i 3, 1 j 3} (8) 4
v(T A ) = P -1 A V A (t 0 )P A T A
where t 0 is the lower bound of the current time interval, P A and V A (t 0 ) describe the screwing associated to the first object. V A (t 0 ) is computed simply from equation (2) by differentiating the matrix elements with respect to time. Similar relations hold for the second OBB. Let vr = v(T A )v(T B ) denote the OBBs centers relative velocity. Then (t 1t 0 )|vr| is approximately the length of the relative path followed by the OBBs centers during the time interval. Thus, the time interval [t 0 ,t 1 ] is subdivided if and only if:

3 ∑ i=1 a i |vr • e i (t 0 )| + (t 1 -t 0 )|vr| > k.( 3 ∑ i=1 b i vr • f i (t 0 )|)
where k is a pre-determined constant. If the time interval isn't subdivided, then the OBBs are declared to have overlapped. Our experiments indicate that most false hit results can be culled when k = 0.2.

Collision detection between primitives

For polyhedral objects, continuous collision detection is somewhat simpler, though more time-consuming, than discrete collision detection since all contact configurations imply at least one of the three non-degenerate contact types: vertex/face, face/vertex, and edge/edge. Moreover, each CD test can be formulated so that the first contact time is a root of a time-dependant function 5,[START_REF] Redon | An Algebraic Solution to the Problem of Collision Detection for Rigid Polyhedral Objects[END_REF][START_REF] Redon | CONTACT: arbitrary in-between motions for continuous collision detection[END_REF] .

For the edge/edge case, a collision is first detected between the lines containing the edges. If a(t)b(t) denotes the first edge and c(t)d(t) denotes the second edge, then a collision occurs when:

a(t)c(t) • (a(t)b(t) × c(t)d(t)) = 0 (9)
The solutions of this equation are computed thanks to the interval-based root-finding method described in Section 3. A solution in [0, 1] is kept if and only if the corresponding contact point belongs to the edges. Note that during the recursive root-finding, when a time interval [t l ,tr] is subdivided into two intervals [t l ,tm] and [tm,tr], solutions are first recursively looked for in [t l ,tm]. If and only if no valid solution is found in this interval, then the second interval [tm,tr] is recursively examined. This allows the process to be stopped as soon as the first contact time has been found.

Collision detection precision

The subdivision method used in the primitive-primitive tests depends on a threshold, which defines the maximal width of an interval that can be subdivided, and thus determines the collision detection precision. The threshold is computed at runtime and depends on the location of the object features.

If dt denotes a small time interval, then the length dl of the helical path followed by an object vertex p is:

dl = |p (t)|dt = s 2 + ω 2 (x 2 + y 2 )dt
where s and ω are the associated screwing parameters and x and y are the first two coordinates of p in the screwing local frame. Let ε 0 denote the maximum error allowed on p's position when the subdivision method completes. Then dl < ε 0 must hold for the last time interval returned. To enforce this, a valid time interval (one which may contain a root) must be subdivided as long as

dt > ε 0 s 2 + ω 2 (x 2 + y 2 ) (11)
Since the contact position can't be known in advance, a similar bound is computed for each of the four vertices a, b, c and d of the current elementary CD test. The interval width threshold is then defined as the lowest of these four bounds. Since the objects primitives (vertices, edges and faces) are convex, this ensures that the error allowed on the contact position will be enforced.

Extension to parametric or implicit surfaces

Using interval analysis to detect collisions between parametric or implicit surfaces amounts to compute at runtime axisaligned bounding-boxes on the objects. For example, let

P : IR 3 → IR 3 x → y = P(x) (12)
denote a parametric surface, and let X denote an interval in IIR 3 . Then Y := P(X) is an interval in IIR 3 . From the inclusion function definition, Y is an axis-aligned box bounding the object part described by X. However, as noted in Snyder et al. 28 , evaluating Y may be highly time-consuming for complex objects, since the structure describing the object (or its inclusion function) has to be traversed.

For rigid parametric or implicit surfaces, a hierarchy of oriented bounding boxes can be precomputed and our continuous OBB/OBB overlap test may be used to quickly cull irrelevant tests, whatever the underlying objects complexity. The actual objects geometry is then tested using Snyder et al.'s algorithms only when two leaf-nodes collide.

Optimizations

This section describes several optimizations added to the system. [START_REF] Redon | CONTACT: arbitrary in-between motions for continuous collision detection[END_REF] , when two objects are processed by the CD functions, a current collision time (CCT) is maintained and passed to the CD functions. For example, when a collision between two edges has been detected at tc ∈ [0, 1], then the next tests (for the pair of objects currently processed) examine only the smaller time interval [0,tc]. Directional traversal When descending an OBB, the child which center is the closest to the center of the OBB belonging to the other object is processed first. Combined to the previous optimization, this allows to rapidly find a preliminary CCT when two fast objects collide, and thus help avoid a quadratic growth of the number of OBB/OBB tests, as would happen if one object passed completely through the other. Partial tests Van den Bergen [START_REF] Van Den Bergen | Efficient collision detection of complex deformable models using AABB trees[END_REF] notices that an axis separating two OBBs is generally an OBB axis, and removes the other nine axes. This results in a moderate speedup in our system. We observed that these nine axes are often useful to separate rotating objects. Coherence tables We have implemented the coherence tables method introduced in Gottschalk [START_REF] Baraff | Curved surfaces and coherence for nonpenetrating rigid body simulation[END_REF] . Briefly, the method consists in storing the terminal nodes of the bounding volumes test tree. When detecting a collision, the bounding volume hierarchies are tested beginning from the terminal nodes of the previous frame. This may be highly memory-consuming, especially for large objects. Moreover, because of the use of the preliminary discrete test, this results in a low speedup (15%), which roughly corresponds to the theoretical limit given by Gottschalk, since a continuous test is approximately five times slower than a discrete one.

Discrete tests

Surprisingly, a usual 'trick' didn't speed up the computations. Pre-computed values of required trigonometric functions (equation ( 2)) were stored in look-up tables. However, this gave no significant result. We conjecture that the compiler already uses such a strategy. Some low-level optimizations have yet to be tried. For example, many processors offer local parallelism through SIMD instructions (single instructions, multiple data). Lin et al. report that a SIMD version of the discrete OBB/OBB overlap test allows a factor 2-3 speedup 20 . Our continuous version should probably benefit from a SIMD implementation. Since profiling reveals that roughly half of the total time is spent during overlap tests between OBBs, this could speed up the whole interactive dynamics simulation significantly. For now, one continuous overlap test is about a few microseconds on a 1 GHz Pentium PC.

Results

A portable collision detection library based upon the algorithms described in this paper has been implemented in C++ and has been successfully tested on Windows and Unix systems. The library has been coupled to analytical (constraintbased) dynamics algorithms [START_REF] Redon | Gauss' least constraints principle and rigid body simulations[END_REF] which take advantage of the precise contact information (first contact instant, contact position and contact normal) sent by the CD functions. The coupling is performed in a classical way 3 . The resulting simulator, running on a 1GHz Pentium PC with 256 Megabytes of memory and the Windows 2000 operating system, is able to perform interactive simulations with models up to tens of thousands of triangles. While it is generally difficult to compare collision detection methods (mainly because CD librairies are not public domain, and because it is difficult to estimate librairies performance on nowadays faster processors from old data), we believe that this couldn't be achieved with previous continuous methods, essentially for the reasons exposed in Section 2.

Several interactive sessions have been specifically designed to test the simulator. No 3D peripherals have been used for interaction. The interface is a 2D mouse, which is sometimes tedious for precise tasks. For sure, the use of a spaceball and stereo glasses would greatly increase the quality of interaction. During an interactive session, the user is able to navigate the scene and can check the validity of collision detection. Moreover, he or she can choose at runtime between a first-order or a second-order simulation. Depending on the world order, the mouse commands the object's velocities or accelerations.

The first application involves 3D models of a few thousand triangles (see Figure 2). It has been designed to test several typical interaction situations (object positioning, slow and fast motions resulting in collisions). This application allows the simulator to be tested for correctness and robustness. As predicted, using arbitrary in-between motions on small time intervals isn't conflicting with realism requirements (according to the user's eye).

Two other applications have been designed to test the approach's scalability. The first one involves a skeleton of a "Renault Scénic" car model (29000 triangles). The car skeleton, manipulated by the user, bounces on a large cubic floor (Figure 3). In the second application, the user must position a car door (16000 triangles, Figure 4) in the car skeleton used in the bouncing test application. Despite unadapted interaction peripherals, the car door can be positioned precisely and interactively with no difficulty (Figures 1 and5). Continuous collision detection, which allows us to achieve very precise object/object interaction, seems essential to the success of this kind of task.

Conclusion and future work

This paper has described a fast continuous collision detection technique which relies upon the effective integration of arbitrary in-between rigid motions, interval arithmetic and OBB hierarchies. An efficient continuous overlap test between two OBBs has been derived from a well-known discrete test. The continuous test consists of two steps. The first step is an interval-based version of the separating tests. The second step is a subdivision test which heuristically determines whether the current time interval should be subdivided when the OBBs are found to overlap. Various optimizations have been described and experimented with. The collision detection algorithms have been coupled to an analytical dynamics simulator which takes advantage of the contact information (first contact time, contact position and contact normal). This interactive dynamics simulator has allowed us to demonstrate the resulting high-quality interaction for models composed of tens of thousands of triangles: the interactive simulation is both robust and precise, since no interpenetration ever occurs.

As noted in the introduction, a major cause of instability in haptics comes from uncontrolled object inter-penetration, since in most algorithms the force exerted by the haptic peripheral depends on the amount of penetration. Actually, the amount of penetration isn't required when a virtual coupling method is used 7 . Thus, we plan to explore haptic interaction with the simulator based upon the algorithms described in this paper.

Figure 1 .

 1 Figure 1. Precise car door positioning. The continuous collision detection technique described in this paper allows to precisely (without any objects interpenetration) and interactively position the door. The car skeleton is about 29000 triangles. The door is about 16000 triangles (3d models ©Renault).

For

  the vertex/face and face/vertex cases, a collision is first detected between the vertex and the plane containing the face. If a(t) denotes the vertex and b(t)c(t)d(t) denotes the triangle, then a collision occurs when: a(t)b(t) • (b(t)c(t) × b(t)d(t)) = 0 (10) In this case, too, solutions are computed using an intervalbased root-finding method. A solution tr in [0, 1] is kept if and only if a(tr) is inside the triangle b(tr)c(tr)d(tr).

Figure 3 .

 3 Figure 3. Second test application: a car skeleton bounces on a large cubic floor. The car is manipulated by the user.

Figure 4 .

 4 Figure 4. A highly-detailed door (16000 triangles). This door is used in the third test application.

Figure 5 .

 5 Figure 5. Third test application: the door being interactively positioned in the car skeleton. Continuous collision detection and constraint-based simulation allows the user to precisely and intuitively position the door. No interpenetration ever occurs.

Figure 6 .

 6 Figure 6. Engine removal. The engine is easily removed from the car door thanks to a 2D mouse (20000 triangles) (3d models ©Renault).

.1.2. Continuous overlap test

  If the OBBs are found to overlap for the current time interval, perform a subdivision test, to determine whether the current time interval should be subdivided. Now let [l 1 , l 2 ] denote a bound on the left side of inequality (7), and let [r 1 , r 2 ] denote a bound on the right side of the same inequality. If l 1 > r 2 , then the axis a is separating the OBBs over the whole time interval. The first step thus consists in performing fifteen such continuous separating axis tests.

	The continuous overlap test is constituted of two steps:
	1. Perform a continuous version of the fifteen separating
	axis tests.
	2. Continuous separating axis tests The first step is easily de-
	rived from the discrete overlap test and interval aritmetic.
	Both sides of inequality (7) are continuous functions of
	time depending on OBBs time-dependent positions. Both
	functions can be bounded using interval arithmetic, as de-
	scribed in Section 3.
	Since we want to continuously detect collisions, we must
	determine whether two moving OBBs overlap during a time
	interval [t 0 ,t 1 ], and not only at the initial or final position. An
	important point is that we only need a conservative overlap
	test. While an overlap occuring between two OBBs must be
	detected, it is not fundamentally a problem to declare that
	an overlap has occured when it hasn't. When the OBB hi-
	erarchies traversal terminates, no collision can have been
	missed. Note that conservative tests are used in other col-
	lision detection methods, for example k-dops 17 . While the
	discrete OBB test is an exact test, the continuous test intro-
	duced in this section is a conservative one.

This first step, however, can only detect an axis which separates two OBBs during the whole interval. Yet, the OBBs may not overlap during a time interval, and be separated by different axes during the motion. This can't be detected by the first step of the continuous test: the fifteen continuous separating axis tests fail, and the OBBs are found to overlap. In interval-based root-finding methods, this problem is solved by subdividing the interval,

  In order to avoid unnecessary continuous OBB/OBB overlap tests, a discrete overlap test is performed for the OBBs initial and final positions before each continuous one. If these discrete tests find that the OBBs overlap, then the continuous test isn't required and thus isn't performed. Since our implementation of the continuous overlap test is approximately five times slower than the one of the discrete overlap test, this results in a significant speedup in high coherency situations. However, it is unuseful in general configurations. Passing the current collision time As in Redon et al.

	Figure 2. First test application: playing with bunnies. The user can
	test typical interaction situations (object positioning, slow and fast
	motions resulting in collisions).

static

© The Eurographics Association and Blackwell Publishers 2002.

© The Eurographics Association and Blackwell Publishers 2002.Redon et al. / Fast Continuous Collision Detection between Rigid Bodies

Aknowledgements

The authors would like to thank Arnaud Buissé for proofreading the submission version, Tangui Morvan for implementing an inventor parser able to convert the Renault models, and Renault for providing the car models. The model parts are ©Renault. The authors would also like to thank the INRIA DISC Multimedia team for producing the accompanying videos. Also, many thanks go to the anonymous reviewers for interesting and useful remarks. This work has been funded by the French Ministry of Research through an AMX grant and the RNTL PERF-RV project.