Peter J Walker

Stuart G Siddell

Elliot J Lefkowitz

Arcady R Mushegian
email: mushegian2@gmail.com

Evelien M Adriaenssens

Poliane Alfenas-Zerbini

Andrew J Davison
email: andrew.davison@glasgow.ac.uk

Donald M Dempsey
email: ddempsey@uab.edu

María Bas E Dutilh
email: bedutilh@gmail.com

Laura García

Elliot J Lefkowi

Arcady R Mushegi

Poliane Alfenas-Zerb

Andrew J Davis

Donald M Demps

Bas E Dutil

• María

Laura Gar

Balázs Harrach
email: harrach.balazs@vmri.hu

Robert L Harri

• R Curtis Hendricks

Sandra Jung

Nick J Knowl

Mart Krupovic

Jens H Kuhn
email: kuhnjens@mail.nih.gov

Amy J Lambert

Małgorzata Łobocka
email: lobocka@ibb.waw.pl

Max L Nibert
email: mnibert@hms.harvard.edu

Hanna M Oksane

Richard J Orto

David L Roberts

Luisa Rubino
email: luisa.rubino@cnr.itseadsabanadzovicssabanadzovic@entomology.msstate.edu

Sead Sabanadzov

Peter Simmonds
email: peter.simmonds@ndm.ox.ac.uk

Donald B Smith
email: donald.smith.ictv@gmail.com

Nobuhiro Suzuki
email: nsuzuki@okayama-u.ac.jp

• Koenraad

V Dooerslaer

Anne-Mieke Vandamme
email: annemie.vandamme@kuleuven.be

Arvind Varsani
email: arvind.varsani@asu.edu

Francisco Murilo Zerbini
email: zerbini@ufv.br

María Laura García
email: garcia_m@biol.unlp.edu.ar

Robert L Harrison
email: robert.l.harrison@ars.usda.gov

R Curtis Hendrickson

Sandra Junglen
email: sandra.junglen@charite.de

Nick J Knowles
email: nick.knowles@pirbright.ac.uk

Hanna M Oksanen
email: hanna.oksanen@helsinki.fi

Richard J Orton
email: richard.orton@glasgow.ac.uk

David L Robertson
email: david.l.robertson@glasgow.ac.uk

Koenraad Van Dooerslaer
email: vandoorslaer@arizona.edu

Changes to virus taxonomy and to the International Code of Virus Classification and Nomenclature ratified by the International Committee on Taxonomy of Viruses (2021)

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Changes to virus taxonomy (the universal scheme of virus classification of the International Committee on Taxonomy of Viruses [ICTV]) take place annually and are the result of a multi-stage process. In accordance with the ICTV Statutes (https:// ictv. global/ statu tes. asp), taxonomic proposals (TaxoProps) submitted to the ICTV Executive Committee (EC) undergo a review process that involves input from the ICTV Study Groups (SGs) and Subcommittees (SCs), other interested virologists, and the EC. After final approval by the EC, proposals are presented for ratification to the full ICTV membership by posting on the ICTV website (https:// ictv. global/), followed by an electronic vote.

The latest set of proposals approved by the EC was made available on the ICTV website in February 2021 (see https:// ictv. global/ propo sal/ MSL36/ for all proposals combined into a single zip file, and use the links provided in the References to access individual proposals). A list of proposals was then emailed on 3rd February 2021 to the 176 members of ICTV, namely the EC Members, Life Members, ICTV SC Members including the SG chairs, and ICTV National Representatives. Members were then requested to vote on whether to ratify the taxonomic proposals. Voting closed on 5th March 2021.

3

Changes to virus taxonomy, to the International Code of Virus Classification and Nomenclature, and to the ICTV Statutes ratified in 2021

All proposals were ratified by ICTV members, in every case receiving an absolute majority of votes; at least 60% of eligible voters approved each proposal. A summary of the taxonomy changes enacted by ratification of the proposals is provided in Table 1. Each proposal is cited and listed in the References to acknowledge the authors' efforts and to provide links to the specific proposal on the ICTV website . These documents remain available for those who wish to see the full details of the proposals. A ratified nontaxonomic proposal 2020.002G [3] specifies a novel procedure for expedited correction of unintended errors that may occur during proposal writing but clearly do not reflect the intention of the proposers, as described in the submitted proposal documentation. Examples of such errors include assignment of a lower-rank taxon to an incorrect higher rank, inadvertent introduction of duplicate taxon names, or assignment of a misspelled taxon name. Since the changes ratified by ICTV take effect immediately, this mechanism was used to correct seven proposals that relate to proposals ratified in March 2021 but were found to contain errors upon crosschecking [18,[START_REF] Kuhn | Correct errors inadvertently introduced into phylum Negarnaviricota taxonomy[END_REF][START_REF] Walker | Correct an error in the spreadsheet for ratified proposal 2020[END_REF][START_REF] Brinton | Correct errors in previous proposals (Nidovirales: Arteriviridae[END_REF]254,255,297].

A notable change approved this year is the adoption of a uniform binomial format for naming of virus species [START_REF] Adriaenssens | Modify the International Code of Virus Classification and Nomenclature (ICVCN) to prospectively mandate a uniform genus-species type virus species naming format[END_REF]. Previously, virologists have not been required to follow the convention of species naming that has been established in other fields of biology, whereby the species name consists of the genus name separated by a space from a species epithet that identifies the species within that genus. Over the last several decades, the case for a standardized nomenclature for virus species has been acknowledged by the ICTV and by many other virologists, but a uniform format of the species names had not been adopted (see references [298][299][300][301][302][303][304] for an incomplete but relatively representative account of the opinion spectrum). The case for a binomial nomenclature was presented by the ICTV Executive Committee in 2018 and 2020, and the advantages and disadvantages of different naming formats within the binomial framework were discussed [305,306]. The EC then invited comments on this position from the virology community. Comments from ICTV SGs were also solicited and received by the EC SCs. Debates of the merits of various forms of binomial nomenclature took place in social media (e.g., 307) and in journal publications [308,309]. Taking these discussions and comments into account, ICTV ratified the adoption of a standardized binomial system, which may follow either Latinized or free form formats [START_REF] Adriaenssens | Modify the International Code of Virus Classification and Nomenclature (ICVCN) to prospectively mandate a uniform genus-species type virus species naming format[END_REF]. The ICTV SGs are now charged with conversion of all existing virus species names to the new binomial form; the process has started already and is expected to be completed in time to be considered by an EC meeting planned for 2023. It is worth emphasizing that this system concerns only the names of virus species but does not affect the names of viruses.

Another general proposal [START_REF] Siddell | Abolish type species[END_REF] was the abolition of the requirement for a type species-a designated nomenclatural type for each genus. The ICTV noted that the requirement for type species in virus taxonomy was largely historical. Most importantly, the ICVCN defines virus species as follows: "A species is a monophyletic group of viruses whose properties can be distinguished from those of other species by multiple criteria", suggesting that the emphasis on "defining" a genus has been shifting from the properties of any particular member to the closeness of molecular and ecological relationships between all genus members. The ICTV concluded that the concept of a type species no longer serves a clear and useful purpose in virology and voted to abolish it. One more proposal [START_REF] Kuhn | Expand, amend, and emend the International Code of Virus Classification and Nomenclature (ICVCN[END_REF] has clarified the remit of the ICTV. In addition to viruses, ICTV has been classifying viroids and virus satellites, though none of these mobile genetic elements, including viruses themselves, have been operationally defined, leaving the limits of the ICTV scope unclear. This has been clarified now by giving operational definitions of viruses sensu stricto, viriforms, viroids, and satellites. These entities together constitute the virosphere and are within the remit of the ICTV responsibilities for their classification, taxonomy and nomenclature. The historical name of the organization-the International Committee on Taxonomy of Viruses-remains unchanged.

Conclusion

All proposals submitted to ratification were ratified by an absolute majority of the ICTV, and the changes are now part of official ICTV taxonomy. An up-to-date list of all approved taxa, which now includes more than 9000 virus species, can be found on the ICTV website: see https:// ictv. global/ propo sal/ MSL36/ for the Master Species List and https:// ictv. global/ vmr/ for the Virus Metadata Resource. Except for Donald M. Dempsey, R. Curtis Hendrickson, Richard J. Orton and Donald B. Smith, the authors were members of the ICTV Executive Committee during the relevant period. The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the US Department of Health and Human Services, or of the institutions and companies affiliated with the authors.

Declarations 1 3

Iridoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 004D.R.

Funding

  E.M.A. gratefully acknowledges funding by the U.K. Biotechnology and Biological Sciences Research Council (BBSRC); this research was funded by the BBSRC Institute Strategic Programme Gut Microbes and Health BB/R012490/1 and its constituent projects BBS/E/F/000PR10353 and BBS/E/F/000PR10356. A.J.D. is supported by the U.K. Medical Research Council (MC_UU_12014/3). B.E.D. is supported by Netherlands Organization for Scientific Research (NWO) Vidi grant 864.14.004. B.H. is supported by the National Research, Development and Innovation Office-NKFIH (NN128309). N.J.K. is partially supported by core funding provided by the Biotechnology and Biological Sciences Research Council, UK. Mention of trade names or commercial products in this publication is solely for the purpose of providing specific information and does not imply recommendation or endorsement by the U.S. Department of Agriculture. USDA is an Equal Opportunity Provider and Employer. This work was supported in part through Laulima Government Solutions, LLC prime contract with the US National Institute of Allergy and Infectious Diseases (NIAID) under Contract No. HHSN272201800013C. J.H.K. performed this work as an employee of Tunnell Government Services (TGS), a subcontractor of Laulima Government Solutions, LLC under Contract No. HHSN272201800013C. A.R.M. is a Program Director at the U.S. National Science Foundation (NSF); the statements and opinions expressed herein are made in a personal capacity and do not constitute endorsement by NSF or the government of the United States. H.M.O was supported by the University of Helsinki and Academy of Finland by funding for FINStruct and Instruct Centre FI, part of Biocenter Finland and Instruct-ERIC. D.L.R. is supported by the U.K. Medical Research Council (MC_UU_1201412). R.J.O. and D.B.S. are supported by the Wellcome Trust (WT108418AIA). S.S. acknowledges partial support from the Special Research Initiative (MAFES), Mississippi State University, and from the National Institute of Food and Agriculture, US Department of Agriculture, Hatch Project 1021494.

Table 1

 1

	Summary of taxonomic changes approved in March	Rank	Total, MSL-35 a New	Moved Abolished Renamed Merged Total, MSL-36 b
	2021	Realm	4	2	0	0	0	0	6
		Kingdom	9	1	0	0	0	0	10
		Phylum	16	1	0	0	0	0	17
		Class	36	3	0	0	1	0	39
		Order	55	4	1	0	1	0	59
		Family	168	22	5	1	1	0	189
		Subfamily 103	33 c	2	0	0	0	136
		Genus	1,421	807	69	3 c,d	10	1	2,224
		Subgenus	68	2 d	0	0	2	0	70
		Species	6,590	2,562 126	30	215	12	9,110
		a Total number of taxa in the ICTV Master Species List prior to 2021 ratification
		b Total number of taxa now recognized and reported in the ICTV Master Species List
		c One new subfamily promoted from genus
		d One new subgenus demoted from genus

  Irido virid ae_ 1nsp. zip. andor.doszpoly@gmail.com 10. Harrison RL, Herniou EA, Jehle JA, Theilmann DA, Burand JP, Krell PJ, van Oers MM, Vlak JM (2020) Create two new genera and eight new species (Lefavirales: Nudiviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 005D.R. Nudiv iridae_ 2ngen_ 8nsp. zip. Robert.L.Harrison@ars.usda.gov 11. Harrison RL, Herniou EA, Jehle JA, Theilmann DA, Burand JP, Create four new genera (Quwivirus, Patagivirus, Bossavirus, Manticavirus) including five new species and two previously unassigned species, and one new species in the genus Varicellovirus (Herpesvirales: Herpesviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 007D.R. Herpe sviri dae_ 4ngen_ 6nsp. zip. andrew. davison@glasgow.ac.uk 13. Tarján ZL, Pénzes JJ, Doszpoly A, Harrach B, Benkő M (2020) Create one new genus (Testadenovirus) and six new species (Rowavirales: Adenoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 008D.R. Adeno virid ae_ 1ngen_ 6nsp. zip. maribenko@gmail. com 14. Fisher M, Harrison T, Nebroski M, Kruczkiewicz P, Rothen-one new species (Caudovirales: Schitoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 075B.R. Huelv avirus. zip. jow12@dsmz.de 141. Adriaenssens EM, Tolstoy I, Kropinski AM, Moraru C, Wittmann J (2020) Create one new subfamily (Humphriesvirinae) including three existing genera (Caudovirales: Schitoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 076B.R. Humph riesv irinae. zip. jow12@dsmz.de 142. Adriaenssens EM, Tolstoy I, Moraru C Kropinski AM (2020) Create three new species in the genus Ilzatvirus (Caudovirales: Siphoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 090B.R. Laroy evirus. zip. Phage.Canada@gmail.com 156. Adriaenssens EM, Tolstoy I, Kropinski AM (2020) Create one new genus (Lastavirus) including two new species (Caudovirales: Podoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 091B.R. Lasta virus. zip. Phage.Canada@gmail.com 157. Kropinski AM, Tolstoy I, Adriaenssens EM, Kabwe M, Tucci J Myoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 098B.R. Marfa virus. zip. Phage.Canada@gmail.com 164. Adriaenssens EM, Tolstoy I, Moraru C, Kropinski AM (2020) Create one new species in the genus Marthavirus (Caudovirales: Myoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 099B.R. Marth avirus. zip. Phage.Canada@gmail.com 165. Oksanen HM, Krupovic M, Jalasvuori M (2020) Create one new family (Matsushitaviridae) including one renamed genus (Hukuchivirus -formerly Gammasphaerolipovirus) moved from the family Sphaerolipoviridae (Halopanivirales) https:// ictv. global/ ictv/ propo sals/ 2020. 100B.R. Matsu shita virid ae. zip. matti.jalasvuori@jyu.fi 166. Adriaenssens EM, Tolstoy I, Kropinski AM, Ramsey J (2020) Create one new genus (Menderavirus) including three new species (Caudovirales: Myoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 101B.R. Mende ravir us. zip. Phage.Canada@gmail.com 167. Adriaenssens EM, Tolstoy I, Kropinski AM, Moraru C, Wittmann J (2020) Create one new subfamily (Migulavirinae) including two existing genera (Caudovirales: Schitoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 102B.R. Migul aviri nae. zip. jow12@ dsmz.de 168. Adriaenssens EM, Tolstoy I, Kropinski AM Ramsey J (2020) Create one new genus (Moabitevirus) including two new species (Caudovirales: Myoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 103B.R. Moabi tevir us. zip. Phage.Canada@gmail.com 169. Adriaenssens EM, Tolstoy I, Kropinski AM (2020) Create one new genus (Moturavirus) including one new species

	(Mononegavirales: Rhabdoviridae) https:// ictv. global/ ictv/
	propo sals/ 2020. 010M.R. Lostr havir us_ 1nsp. zip. peter.walker@
	uq.edu.au
	35. Balkema-Buschmann A, Dundon WG, Duprex WP, Easton AJ,
	Fouchier RAM, Kurath G, Lamb RA, Lee B, Rima BK, Rota
	PA, Wang LF (2020) Create one new species (Avian metaavu-
	Krell PJ, van Oers MM (2020) Create one new class (Naldaviri-cetes) including one new order (Lefavirales) for four families of arthropod-specific large DNA viruses https:// ictv. global/ ictv/ propo sals/ 2020. 006D.R. Nalda viric etes. zip. Robert.L.Harrison@ ars.usda.gov 12. Gatherer D, Benkő M, Brandt CR, Bryant NA, das Neves CG, Dastjerdi A, Depledge DP, Doszpoly A, Gompels UA, Hartley CA, Inoue N, Jarosinski KW, Kaul R, Lacoste V, Norberg P, Origgi FC, Orton RJ, Pellett PE, Schmid DS, Spatz SJ, Stew-art JP, Szpara ML, Trimpert J, Vaz P, Waltzek TB, Davison AJ (2020) Arvind.varsani@asu.edu 16. Penzes JJ, Canuti M, Söderlund-Venermo M, Eis-Huebinger AM, Ogliastro M, Harrach B (2020) Create three new genera and 19 new species (Piccovirales: Parvoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 011D.R. Parvo virid ae_ 3ngen_ 20nsp. zip. judit. penzes@ufl.edu 17. Hepojoki J, Hetzel U, Paraskevopoulou S, Drosten C, Harrach B, Zerbini M, Koonin EV, Krupovic M, Dolja V, Kuhn JH (2020) Create one new realm (Ribozyviria) including one new fam-ily (Kolmioviridae) including genus Deltavirus and seven new genera for a total of 15 species https:// ictv. global/ ictv/ propo sals/ 2020. 012D.R. Riboz yviria. zip. jussi.hepojoki@helsinki.fi 18. Harrach B (2020) Correct the misspelt name of one species (Bluegill hepatitis B virus) in the genus Metahepadnavirus (Blu-bervirales: Hepadnaviridae) https:// ictv. global/ ictv/ propo sals/ lavirus 22) in the genus Metaavulavirus (Mononegavirales: Paramyxoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 011M.R. Metaa vulav irus_ 1nsp. zip. b.rima@qub.ac.uk 36. Hughes HR (2020) Create 16 new species and abolish one spe-cies in the genus Orthobunyavirus (Bunyavirales: Peribunya-viridae) https:// ictv. global/ ictv/ propo sals/ 2020. 012M.R. Ortho bunya virus_ 16new_ sp_ aboli sh_ 1sp. zip. LTR8@cdc.gov 37. Dietzgen RG, Freitas-Astúa J, Kondo H, Whitfield AE, Bejer-man N, Debat H, Walker PJ (2020) Create two new species in the genus Alphanucleorhabdovirus, three new species in the genus Betanucleorhabdovirus, two new species in the genus Cytorhabdovirus and two new species in the genus Varicosa-virus (Mononegavirales: Rhabdoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 013M.R. Plant_ rhabd oviru ses_ 9nsp. zip. r.dietzgen@uq.edu.au 38. Walker PJ, Blasdell KR, Dietzgen RG, AR, Fooks, Freitas-Astúa J, Kondo H, Kuzmin IV, Tesh RB, Vasilakis N, Whitfield AE (2020) Create one new genus (Alphapaprhavirus) includ-ing two new species (Mononegavirales: Rhabdoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 014M.R. Alpha paprh avirus_ 1gen2 sp. zip. peter.walker@uq.edu.au 39. Walker PJ, Blasdell KR, Dietzgen RG, Fooks AR, Freitas-Astúa J, Kondo H, Kuzmin IV, Tesh RB, Vasilakis N, Whitfield AE (2020) Create one new genus (Merhavirus) including two new species (Mononegavirales: Rhabdoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 015M.R. Merha virus_ 1gen2 nsp. zip. peter.walker@uq.edu.au 40. Walker PJ, Blasdell KR, Breyta R, Dietzgen RG, Fooks AR, Freitas-Astúa J, Kondo H, Kurath G, Kuzmin IV, Stone DM, Tesh RB, Tordo N, Vasilakis N, Whitfield AE (2020) Create three new subfamilies in the family Rhabdoviridae (Mononega-virales) https:// ictv. global/ ictv/ propo sals/ 2020. 016M.R. Rhabd oviri dae_ 3subf am. zip. peter.walker@uq.edu.au 41. Shi Z-L, Kuhn JH, Lukashevich IS, Clegg JCS, Gonzalez J-PJ, de la Torre JCC, Hepojoki J, Salvato M, Stenglein M, Buchmeier MJ, Charrel RN, Radoshitzky SRR, Günther S, Romanowski V, de Lamballerie X, Sironi M, Agwanda B (2020) Create one new species in genus Mammarenavirus (Bunyavirales: Arenaviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 017M.R. Mamma renav irus. zip. zlshi@wh.iov.cn 42. Mordecai GJ, Miller KM, Di Cicco E, Schulze AD, Kaukinen KH, Ming TJ, Li S, Tabata A, Teffer A, Patterson DA, Fergu-son HW, Suttle CA (2020) Create one new species in genus Antennavirus (Bunyavirales: Arenaviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 018M.R. Anten navir us. zip. gidmord@ gmail.com 43. Hepojoki J (2020) Create two new species in the genus Hart-Siphoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 077B.R. Ilzat virus. zip. Phage.Canada@gmail.com 143. Adriaenssens EM, Tolstoy I, Kropinski AM, Barylski J (2020) Create one new genus (Jarrellvirus) including one new species (Caudovirales: Siphoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 078B.R. Jarre llvir us. zip. Jakub.Barylski@gmail.com 144. Adriaenssens EM,Tolstoy I, Kropinski AM, Morozova V, Bar-ylski J (2020) Create one new genus (Kamchatkavirus) includ-ing one new species (Caudovirales: Siphoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 079B.R. Kamch atkav irus. zip. Jakub. Barylski@gmail.com 145. Kropinski AM, Adriaenssens EM, Turner D (2020) Create one new genus (Kanagawavirus) including two new species (Cau-dovirales: Myoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 080B.R. Kanag awavi rus. zip. Phage.Canada@gmail.com 146. Adriaenssens EM, Tolstoy I, Turner D, Kropinski AM (2020) Create one new genus (Karimacvirus) including five new species (Caudovirales: Siphoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 081B.R. Karim acvir us. zip. Phage.Canada@gmail.com 147. Kropinski AM, Adriaenssens EM, Neve H, Franz CMAP, Sprotte S (2020) Create one new genus (Knuthellervirus) including one new species (Caudovirales: Siphoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 082B.R. Knuth eller virus. zip. Phage.Canada@ gmail.com 148. Kropinski AM, Turner D, Adriaenssens EM (2020) Create one new genus (Kozyakovvirus) including one new species (Cau-dovirales: Podoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 083B.R. Kozya kovvi rus. zip. Phage.Canada@gmail.com 149. Adriaenssens EM, Tolstoy I, Moraru C, Kropinski AM (2020) Create one new genus (Kuleanavirus) including one new species (Caudovirales: Siphoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 084B.R. Kulea navir us. zip. Phage.Canada@gmail.com 150. Adriaenssens EM, Tolstoy I, Kropinski AM (2020) Create one new genus (Kungbxnavirus) including one new species (Cau-dovirales: Myoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 085B.R. Kungb xnavi rus. zip. Phage.Canada@gmail.com 151. Adriaenssens EM, Tolstoy I, Turner D, Kropinski AM (2020) Create one new genus (Kylevirus) including one new species (Caudovirales: Myoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 086B.R. Kylev irus. zip. Phage.Canada@gmail.com 152. Kabwe M, Petrovski S, Tucci J, Adriaenssens EM, Tolstoy I, Kro-pinski AM (2020) Create one new genus (Lahexavirus) including four new species (Caudovirales: Podoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 087B.R. Lahex avirus. zip. Phage.Canada@	(2020) Create one new genus (Latrobevirus) including one new species (Caudovirales: Siphoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 092B.R. Latro bevir us. zip. Phage.Canada@gmail. com 158. Adriaenssens EM, Tolstoy I, Turner D, Kropinski AM (2020) Create one new genus (Leicestervirus) including three new spe-cies (Caudovirales: Siphoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 093B.R. Leice sterv irus. zip. Phage.Canada@gmail.com 159. Adriaenssens EM, Tolstoy I, Moraru C Kropinski AM (2020) Create one new genus (Seongbukvirus) including one new spe-cies and create four new species of Leuconostoc phages in two existing genera (Caudovirales: Siphoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 094B.R. Leuco nostoc_ sipho virus es. zip. Phage.Canada@gmail.com 160. Callanan J, Stockdale SR, Adriaenssens EM, Kuhn JH, Rumnieks J, Shkoporov A, Draper LA, Ross RP, Hill C (2020) Rename one class (Leviviricetes -formerly Allassoviricetes), rename one order (Norzivirales -formerly Levivirales), create one new order (Timlovirales), and expand the class to a total of six families, 420 genera and 883 species https:// ictv. global/ ictv/ propo sals/ 2020. 095B.R. Leviv irice tes. zip. c.hill@ucc.ie 161. Truncaitė L, Kropinski AM, Adriaenssens EM, Šimoliūnas E (2020) Create one new genus (Lietduovirus) including one new species (Caudovirales: Myoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 096B.R. Lietd uovir us. zip. Phage.Canada@gmail.com 162. Wittmann J, Adriaenssens EM, Kropinski AM (2020) Create one new genus (Littlefixvirus) containing one new species (Cau-dovirales: Schitoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 097B.R. Littl efixv irus. zip. Johannes.Wittmann@dsmz.de 163. Kropinski AM, Tolstoy I, Turner D, Adriaenssens EM (2020) Create one new genus (Marfavirus) including two new species (Caudovirales: Quadram Institute Bioscience, Norwich Research Park, Norwich NR4 7UQ, UK
	2020. 013D.R. Metah epadn avirus_ 1sp. zip. balazs.harrach@gmail. com 19. Kraberger S, Opriessnig T, Varsani A (2020) Create nine new species in the genus Gyrovirus (Anelloviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 014D.R. Gyrov irus_ 9nsp. zip. Arvind.var-sani@asu.edu manivirus (Bunyavirales: Arenaviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 019M.R. Hartm anivi rus. zip. jussi.hepojoki@ helsinki.fi 44. Ballinger MJ, Hall RA, Langevin SA, Pauvolid-Corrêa A, Par-askevopoulou S, Drosten C, Junglen S (2020) Create four new species in the genus Orthophasmavirus, create two new species gmail.com 153. Adriaenssens EM, Tolstoy I, Turner D, Kropinski AM (2020) Create one new genus (Lambovirus) including five new species (Caudovirales: Siphoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 088B.R. Lambo virus. zip. Phage.Canada@gmail.com 154. Kropinski AM, Tolstoy I, Turner D, Adriaenssens EM (2020)	6 7	Departamento de Microbiologia, Universidade Federal de Viçosa, Viçosa, MG 36570-000, Brazil MRC-University of Glasgow Centre for Virus Research, Sir Michael Stoker Building, 464 Bearsden Road, Glasgow G61 1QH, UK
	20. Varsani A, Kraberger S (2020) Create 17 genera and new 80 species (Anelloviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 015D.R. Anell oviri dae_ 17ngen_ 80nsp. zip. Arvind.Varsani@asu. edu in the genus Feravirus and create one new genus (Hymovirus) including two new species (Bunyavirales: Phasmaviridae) Create 12 new genera including 17 new species for Lactobacil-lus viruses (Caudovirales: Siphoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 089B.R. Lacto bacil lus_ sipho virus es. zip. Phage. Canada@gmail.com	8	Theoretical Biology and Bioinformatics, Department of Biology, Utrecht University, Padualaan 8, Room Z-509, 3584 CH Utrecht, The Netherlands
	21. Varsani A, Krupovic M (2020) Create six new genera and 42 155. Adriaenssens EM, Tolstoy I, Moraru C, Kropinski AM (2020)
	new species (Cremevirales: Smacoviridae) https:// ictv. global/ Create three new species in the genus Laroyevirus (Caudovirales:
			1 3

burger J, Ambagala A, Macbeth B, Lung O (2020) Create one new species in the genus Circovirus (Circlivirales: Circoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 009D.R. Circo virus_ 1nsp. zip. oliver.lung@canada.ca 15. Varsani A, Rosario K, Delwart E, Segales J, Breitbart M (2020) Create six new species in the genus Circovirus and one new species in the genus Cyclovirus (Circlivirales: Circoviridae) https:// ictv. global/ ictv/ propo sals/ 2020. 010D.R. Circo virid ae_ 7nsp. zip. https:// ictv. global/ ictv/ propo sals/ 2020. 020M.R. Phasm aviri dae. zip. sandra.junglen@charite.de 45. Walker PJ, Bennett AJ, Kuhn JH, Goldberg TL (2020) Create one new species (Bughendera ledantevirus) in the genus Ledantevirus (Mononegavirales: Rhabdoviridae) https:// ictv. global/ ictv/ 1 3

Conflict of interest

The authors declare no conflicts of interest Human and animal rights statement None of the work reported involved research on human participants or animals. All authors have contributed to this work and agreed to its publication.


B Vallet

B Lévy

Spectral Geometry Processing with Manifold Harmonics

Keywords: Descriptors (according to ACM CCS): I, 3, 5 [Computer Graphics]: Computational Geometry and Object Modeling, Hierarchy and geometric transformations

We present an explicit method to compute a generalization of the Fourier Transform on a mesh. It is well known that the eigenfunctions of the Laplace Beltrami operator (Manifold Harmonics) define a function basis allowing for such a transform. However, computing even just a few eigenvectors is out of reach for meshes with more than a few thousand vertices, and storing these eigenvectors is prohibitive for large meshes. To overcome these limitations, we propose a band-by-band spectrum computation algorithm and an out-of-core implementation that can compute thousands of eigenvectors for meshes with up to a million vertices. We also propose a limited-memory filtering algorithm, that does not need to store the eigenvectors. Using this latter algorithm, specific frequency bands can be filtered, without needing to compute the entire spectrum. Finally, we demonstrate some applications of our method to interactive convolution geometry filtering. These technical achievements are supported by a solid yet simple theoretic framework based on Discrete Exterior Calculus (DEC). In particular, the issues of symmetry and discretization of the operator are considered with great care.

Introduction

3D scanning technology easily produces computer representations from real objects. However, the acquired geometry often presents some noise that needs to be filtered out. More generally, it may be suitable to enhance some details while removing other ones, depending on their sizes (spatial frequencies). In his seminal paper, Taubin [START_REF] Taubin | A signal processing approach to fair surface design[END_REF] showed that the formalism of signal processing can be successfully applied to geometry processing. His approach is based on the similarity between the eigenvectors of the graph Laplacian and the basis functions used in the discrete Fourier transform. This Fourier function basis enables a given signal to be decomposed into a sum of sine waves of increasing frequencies. He used this analogy as a theoretical tool to design and analyse approximations of low-pass filters. Several variants of this approach were then suggested, as discussed below.

In this paper, instead of only using Fourier analysis as a theoretical tool to analyse approximations of filters, our idea is to explicitly implement its generalization to surfaces of arbitrary topology, and use this to achieve interactive general convolution filtering. Our processing pipeline is similar to the one described in [START_REF] Gross | Spectral processing of point sampled geometry[END_REF] for point sets. The main difference is that no resampling nor segmentation is needed: the Fourier transform is computed directly on the mesh. The pipeline is outlined in Figure 1: • A: given a triangulated mesh with n vertices, compute a function basis H k , k = 1 . . . m that we call the Manifold Harmonics Basis (MHB). The k th element of the MHB is a piecewise linear function given by its values H k i at vertices i of the surface; • C: apply a frequency space filter F(ω) by multiplying each ( xk , ỹk , zk ) by F(ω k ), where ω k denotes the frequency associated with H k ;

• D: finally, transform the object back into geometric space by applying the inverse MHT. Note that this approach shares some similarities with signal processing with spherical harmonics or with the Discrete Cosine Transform. The main difference is that our approach does not require any resampling of the original surface. However, our MHB depends on the surface, and therefore requires to be precomputed (step A). Once the MHB is known, the subsequent stages of the pipeline can be very efficiently computed. This allows the solution to be interactively updated when the F(ω) filter is modified by the user.

Contributions

The main contribution of this paper is an efficient numerical mechanism to compute the eigenfunctions of the Laplacian that overcomes the current limits (thousands vertices) by several orders of magnitude (up to a million vertices). The eigenfunctions are computed band by band based on spectral transforms and an efficient eigensolver, and an out-of-core implementation that can compute thousands of eigenvectors for meshes with up to a million vertices. We also propose a limited-memory filtering algorithm, that does not need to store the eigenvectors. Once computed, the MHB allows for interactive filtering on meshes which we demonstrate applied to geometry. These computations use a clean, rigorous yet simple DEC-based framework which clarifies the issues of weighting and symmetry of the discrete cotangent Laplacian. In particular, the symmetry guaranties that the eigenfunctions form an orthonormal "Manifold Harmonics Basis" (MHB) with positive eigenvalues.

Previous Work

The discretization of the Laplacian operator plays a central role in geometry processing and has been extensively stud-ied, motivated by the large number of its applications, that include parameterization, remeshing, compression, reconstruction and minimal surfaces. The eigenfunctions of the Laplacian are known to define a Fourier-like function basis [START_REF] Zhang | Spectral methods for mesh processing and analysis[END_REF], that can be used to define spectral analysis on manifolds. We will now review some of the most significant definitions and applications of discrete Laplacians, focusing mainly on the works related with spectral analysis and geometric filtering.

Combinatorial Laplacians: A combinatorial Laplacian solely depends on the connectivity of the mesh. Spectral analysis of the combinatorial graph Laplacian was first used by Taubin [START_REF] Taubin | A signal processing approach to fair surface design[END_REF] to approximate low pass filters. A basis of eigenfunctions of the graph Laplacian was used by Karni et al. [START_REF] Karni | Spectral compression of mesh geometry[END_REF] for geometry compression. Zhang [START_REF] Zhang | Discrete combinatorial laplacian operators for digital geometry processing[END_REF] studies several variants of combinatorial laplacians and their properties for spectral geometry processing and JPEG-like mesh compression. However, as pointed-out in [START_REF] Meyer | Discrete differential-geometry operators for triangulated 2-manifolds[END_REF], the analogy between the graph Laplacian and the discrete cosine transform supposes a uniform sampling of the mesh. Moreover, different embeddings of the same graph yield the same eigenfunctions, and two different meshings of the same object yield different eigenfunctions which is problematic as shown in Figure 2.

Geometric Laplacians and applications: More geometry can be injected into the definition of a discrete Laplacian through the ubiquitous cotan weights [START_REF] Pinkall | Computing discrete minimal surfaces and their conjugates[END_REF][START_REF] Meyer | Discrete differential-geometry operators for triangulated 2-manifolds[END_REF]. These weights can also be derived from Finite Element Modeling (FEM) such as done in [WBH * 07], and they converge to the continuous Laplacian under certain conditions as explained in [START_REF] Hildebrandt | On the convergence of metric and geometric properties of polyhedral surfaces[END_REF] and [START_REF] Arnold | Finite element exterior calculus, homological techniques, and applications[END_REF]. Reuter et al. [START_REF] Reuter | Laplace-spectra as fingerprints for shape matching[END_REF] also use FEM to compute the spectrum (i.e. the eigenval-Figure 2: Filtering an irregularly sampled surface (twice denser on the right half) with different discrete laplacians. Combinatorial Laplacian (A), unweighted cotan cot(β i j ) + cot(β i j ) (B) and symmetrized weighted cotan (cot(β i j ) + cot(β i j ))/(A i + A j ) (D) produce deformed results (right leg is bigger). Weighted cotan (cot(β i j ) + cot(β i j ))/A i are not symmetric which does not allow for correct reconstruction (C). Only our symmetric weights (cot(β i j ) + cot(β i j ))/ A i A j are fully mesh-independent (E).

ues) of a mesh, which provides a signature for shape classification. The cotan weights were also used in [DBG * 06] to compute an eigenfunction to steer a quad-remeshing process. The cotan weights alone are still dependent on the sampling as shown in Figure 2-B, so they are usually weighted by the one ring or dual cell area of each vertex, which makes them loose their symmetry. As a consequence, they are improper for spectral analysis (2-C). An empirical symmetrization was proposed in [START_REF] Levy | Laplace-beltrami eigenfunctions: Towards an algorithm that understands geometry[END_REF] (see Figure 2-D). We clarify these issues based on a rigorous DEC formulation, and recover symmetry by expressing the operator in a proper basis. This ensures that its eigenfunctions are both geometry aware and orthogonal (Figure 2-E). Note that a recent important proof [START_REF] Wardetzky | Discrete laplace operators: No free lunch[END_REF] states that a "perfect" discrete Laplacian that satisfies all the properties of the continuous one cannot exist on general meshes. This explains the large number of definitions for a discrete Laplacian, depending on the desired properties.

Laplacian based Geometric Filtering: A Laplacian-based geometric filtering method was recently proposed [START_REF] Rossignac | GeoFilter: Geometric Selection of Mesh Filter Parameters[END_REF] and was applied to a wide class of filters (e.g. bandexaggeration). This method combines explicit and implicit schemes to reach the different frequency bands involved in the filter. In comparison, our method can use arbitrary userdefined filters, and offers in addition the possibility of changing the filter interactively.

Geometric filtering through energy minimization: Other approaches to geometric filtering are based on energy minimization (e.g. [START_REF] Mallet | Discrete Smooth Interpolation[END_REF]). These methods are called discrete fairing in [START_REF] Kobbelt | Discrete fairing[END_REF][START_REF] Kobbelt | Interactive multi-resolution modeling on arbitrary meshes[END_REF], in reference to their continuous-setting counterparts [START_REF] Bloor | Using partial differential equations to generate free-form surfaces[END_REF]. Recently, a method was proposed [START_REF] Nealen | Laplacian mesh optimization[END_REF] to optimize both inner fairness (tri-angle shapes) and outer fairness (surface smoothness), by using a combination of the combinatorial Laplacian and the discrete Laplace-Beltrami operator.

Spectral transform: To directly implement the spectral transform on manifolds, several methods consist in putting the input surface in one-to-one correspondence with a simpler domain [START_REF] Zhou | 3d surface filtering using spherical harmonics[END_REF], or to partition it into a set of simpler domains [LSS * 98, PG01] on which it is easier to define a frequency space. Note that these methods generally need to resample the geometry, with the exception of Mousa et al. [START_REF] Mousa | Direct spherical harmonic transform of a triangulated mesh[END_REF] who directly compute the Spherical Harmonic Transform of a star-shaped mesh. It is also possible to extract the frequencies from a progressive mesh [LSS * 98] and avoid resampling the geometry by using irregular subdivision [START_REF] Guskov | Multiresolution signal processing for meshes[END_REF]. Finally, an original approach is presented in [SCOIT05] that computes "geometry aware" basis functions, defined as solutions of some least-squares problems.

Our method computes the frequency-space basis functions as eigenvectors of a symmetric matrix, for a surface of arbitrary topology without needing any resampling nor segmentation.

The rest of the paper is organized as follows. We first recall some notions on the Fourier Analysis (Section 2.1). A Manifold Harmonics Basis (MHB) is then built through a DEC formulation, and its relations with the classical discrete Laplacian is explained (Section 2.2). Equipped with this new tool, it is then simple to generalize spectral analysis and Fourier transform to arbitrary manifolds. This defines the Manifold Harmonics Transform (MHT) that transforms from geometric space into frequency space, and the inverse MHT (Section 3). We finally explain how to efficiently compute the MHB in practice, and how to implement scalable spectral geometry processing (Section 4). We conclude by presenting some applications and results.

Spectral Analysis on Manifolds

Manifold harmonics (also called shape harmonics) are defined as the eigenfunctions of the Laplace operator. This section starts by recalling the familiar Fourier analysis to justify the choice of the eigenfunctions of the Laplace operator to generalize this setting to arbitrary manifolds. We will then define the Laplace operator in the DEC setting and justify a symmetric weighting ensuring the orthogonality of the MHB.

Fourier Analysis

Given a square-integrable periodic function f :

x ∈ [0, 1] → f (x)
, or a function f defined on a closed curve parameterized by normalized arclength, it is well known that f can be expanded into an infinite series of sines and cosines of increasing frequencies:

f (x) = ∞ ∑ k=1 fk H k (x) ; H 2k = sin(kx) H 2k+1 = cos(kx) (1)
where the coefficients fk of the decomposition are given by:

fk =< f , H k >= 1 0 f (x)H k (x)dx (2)
and where < ., . > denotes the inner product (i.e. the "dot product" for functions defined on [0, 1]). The "Circle harmonics" basis H k is orthonormal with respect to < ., . >:

< H k , H k >= 1, < H k , H l >= 0 if k = l.
The set of coefficients fk (Equation 2) is called the Fourier Transform (FT) of the function f . Given the coefficients fk , the function f can be reconstructed by applying the inverse Fourier Transform FT -1 (Equation 1). Our goal is now to generalize these notions to arbitrary manifolds. To do so, we can consider the functions H k of the Fourier basis as the eigenfunctions of -∂ 2 /∂ x 2 : the eigenfunctions H 2k (resp. H 2k+1 ) are associated with the eigenvalues k 2 :

- ∂ 2 H 2k (x) ∂ x 2 = k 2 sin(kx) = k 2 H 2k (x)
To extended this construction to arbitrary manifolds, we need to generalize both inner product < ., . > and secondorder derivative ∂ 2 /∂ x 2 to arbitrary manifolds. We now explain how Discrete Exterior Calculus (DEC) helps doing so.

DEC for spectral analysis

For a complete introduction to DEC we refer the reader to [START_REF] Desbrun | Dis-crete differential forms for computational modeling[END_REF], [START_REF] Hirani | Discrete exterior calculus[END_REF] and to [START_REF] Arnold | Finite element exterior calculus, homological techniques, and applications[END_REF] for proofs of convergence. We quickly introduce the few notions and notations that we are using to define the inner product < ., . > and generalized second-order derivative (i.e. Laplacian operator).

A k-simplex s k is the geometric span of k + 1 points. For instance, 0, 1 and 2-simplices are points, edges and triangles respectively. In our context, a mesh can be defined as a 2-dimensional simplicial complex S, i.e. a collection of n k k-simplices (k = 0, 1, 2), with some conditions to make it manifold. A discrete k-form ω k on S is given by a real value ω k (s k ) associated with each oriented k-simplex (that corresponds to the integral of a smooth k-form over the ksimplex). The set Ω k (S) of k-forms on S is a vector space of dimension n k . With a proper numbering of the k-simplices, ω k can be assimilated to a vector of size n k , and linear operators from Ω k (S) to Ω l (S) can be assimilated to (n k , n l ) matrices.

The exterior derivative d k : Ω k (S) → Ω k+1 (S) is defined by the signed adjacency matrix:

(d k ) s k ,s k+1 = ±1 if s k belongs
to the boundary of s k+1 , with the sign depending on their respective orientations.

DEC provides Ω k (S) with a L 2 inner product:

< ω k 1 , ω k 2 >= (ω k 1 ) T k ω k 2 ( 3
)
where k is the so-called Hodge star. As a matrix, the Hodge star is diagonal with elements |s * k |/|s k | where s * k denotes the circumcentric dual of simplex s k , and |.| is the simplex volume. In particular, for vertices, edges and triangles:

( 0 ) vv = |v * | ; ( 1 ) ee = |e * | |e| = cot β e + cot β e ;
where β e and β e denote the two angles opposite to e.

Finally the Laplace de Rham operator on 0-forms is given by: ∆ = --1 0 d T 1 1 d 0 and its coefficients are:

∆ i j = - cot(β i j ) + cot(β i j ) |v * i | ; ∆ ii = -∑ j ∆ i j
For surfaces with borders, if the edge i j is on the border, the term cot(β i j ) vanishes and the dual cell v * i is cropped by the border. This matches the FEM formulation (see [START_REF] Hildebrandt | Finite elements for the beltrami operator on arbitrary surfaces. Partial differential equations and calculus of variations[END_REF] or [START_REF] Vallet | Manifold Harmonics[END_REF]) with Neumann boundary conditions, with the difference that FEM has a mass matrix (corresponding to 0 ) which is not diagonal and which terms consist of one ring areas (whereas 0 contains dual cell areas). This comes from the fact that DEC is based on a mixed Finite Elements/Finite Volumes scheme where the elements are the same as in FEM but the volumes are the dual cells. This difference has litte impact, especially as the mass matrix is often diagonalized (lumped mass approximation) in FEM formulations.

Remark:

The matrix ∆ corresponds to the standard discrete Laplacian, except for the sign. The sign difference comes from the distinction between Laplace-Beltrami and Laplace de Rham operators. eigenfunction basis no longer orthonormal, which is problematic for our spectral processing purposes (Figure 2-C). To recover symmetry, consider the canonical basis (φ i ) of 0forms: φ i = 1 on vertex i and φ i = 0 on other vertices. This basis is orthogonal but not normal with respect to the inner product defined in Equation 3 (< φ i , φ i >= (φ i ) T 0 φ i = 1). However, since the Hodge star 0 is a diagonal matrix, one can easily normalize (φ i ) as follows:

φi = -1/2 0 φ i
In this orthonormalized basis ( φi ), the Laplacian ∆ is symmetric, and its coefficients are given by:

∆ = -1/2 0 ∆ -1/2 0 ; ∆i j = - cot β i j + cot β i j |v * i ||v * j | (4)

The Manifold Harmonic Basis (MHB)

Given these definitions, we can now compute the MHB, defined to be the set of eigenvectors of ∆ expressed in the canonical basis:

1. Assemble the discrete Laplacian ∆ (see Equation 4);

2. Compute its eigenvectors ( Hk ) (see Section 4);

3. Map them into the canonical basis:

(H k ) = ( -1/2 0 Hk ).
The set of so-obtained (H k ) vectors is called the Manifold Harmonics basis (MHB). An example is shown in Figure 3. Note that by construction, the MHB is orthonormal with respect to the inner product. This property is important to define the associated transforms, as explained below.

The Manifold Harmonic Transform

Transforming 0-forms between the canonical basis (φ k ) i.e., geometric space and the MHB (H k ) i.e., frequency space will be called the Manifold Harmonic Transform (MHT). It is also easy to define the inverse transform (MHT -1 ). They generalize the notion of Fourier transform to simplicial complexes. We now derive the expressions of MHT and MHT -1 , and apply them to geometry filtering.

MHT and inverse MHT

We consider the geometry x (resp. y,z) of the simplicial complex S, that can be seen as a piecewise linear function. In other words, x is a linear combination of the canonical basis functions φ i :

x = n ∑ i=1 x i φ i (5)
where x i denotes the x coordinate at vertex i. Computing the MHT means projecting the function x into the MHB, i.e. finding the coefficients xk such that:

x = m ∑ k=1 xk H k (6)
Since the MHB is orthonormal, we can easily project (5) and ( 6) onto each H k with the inner product:

< x, H k > = ∑ n i=1 x i < φ i , H k >= x T 0 H k < x, H k > = ∑ m
k=1 xk < H k , H k >= xk By equating both expressions, we finally obtain the expression of xk :

xk = x T 0 H k = n ∑ i=1 x i ( 0 ) ii H k i (7)
Using these equations, we know how to transform 0-forms between geometric space (x) and frequency space ( x). This defines the MHT and inverse MHT: 7) 6)

• MHT: (x i ) → ( xk ) (Equation
• MHT -1 : ( xk ) → (x i ) (Equation
Figure 4 shows the geometry reconstructed from the MHT of a surface using a different number m of MHT coefficients.

As can be seen, the first H k functions capture the general shape of the functions and the next ones correspond to the details.

Filtering

Once the geometry is converted into the MHB, each component ( xk , ỹk , zk ) of the MHT corresponds to an individual spatial frequency ω k . In the case of a closed curve (Section 2.1), we have -∂ 2 sin(ωx)/∂ x 2 = ω 2 sin(ωx). Therefore, the spatial frequency ω k corresponds to the square root of the eigenvalue λ k . In the case of a manifold, similar results can be obtained, that connect ω k = λ k with the length of the nodal sets [START_REF] Donnelly | Nodal sets of eigenfunctions on riemannian manifolds[END_REF].

A frequency-space filter is a function F(ω) that gives the amplification to apply to each spatial frequency ω. Since all frequencies are separated by the MHT, applying a filter F(ω) to the geometry becomes a simple product in frequency space. The filtered coordinate x F i (resp y F i , z F i ) at vertex i is then given by:

x F i = m ∑ k=1 F(ω k ) xk H k i = m ∑ k=1 F( λ k ) xk H k i
In practice, we stop computing the MHB at a given "cutoff" frequency ω m = √ λ m (inverse of 10 times the average edge length in our experiments). Therefore, smaller geometric details are not represented in the MHT. However, it is possible to keep track of them, by storing in each vertex the difference x h f i (resp. y h f i , z h f i ) between the original geometry and its projection onto the MHB:

x h f i = ∞ ∑ k=m+1 xk H k i = x i - m ∑ k=1 xk H k i
The frequency-space filter can be applied to the highfrequency components of the signal, by re-injecting them into the inverse MHT, as follows:

x F i = m ∑ k=1 F(ω k ) xk H k i + f h f x h f (8)
In this equation, the term f h f denotes the average value of the filter F on [ω m , ω M ], where ω M denotes the maximum (Nyquist) frequency of the mesh (half the inverted edge length). The high-frequency component behaves like a wave packet that can be filtered as a whole, but that cannot be considered as independent frequencies.

Figure 5 demonstrates low-pass, enhancement and bandexaggeration filters. Note that unlike existing methods, ours does not need to re-scale the model. Moreover, only the filtered inverse MHT (Equation 8) depends on the filter F. As a consequence, after storing the MHB and the MHT coefficients, the solution can be updated interactively when the user changes the filter F.

We now proceed to explain how to compute the coefficients H k i of the MHB and the associated eigenvalues λ k .

Numerical Solution Mechanism

Computing the MHB means solving for the eigenvalues λ k and eigenvectors Hk for the symmetric positive semi-definite matrix ∆:

∆ Hk = λ k Hk (9)
However, eigenvalues and eigenvectors computations are known to be extremely computationally intensive. To reduce the computation time, Karni et al. [START_REF] Karni | Spectral compression of mesh geometry[END_REF] partition the mesh into smaller charts, and [DBG * 06] use multiresolution techniques. In our case, we need to compute multiple eigenvectors (typically a few thousands). This is known to be currently impossible for meshes with more than a few thousand vertices [START_REF] Wu | Efficient spectral watermarking of large meshes with orthogonal basis functions[END_REF]. In this section, we show how this limit can be overcome by several orders of magnitude.

To compute the solutions of large sparse eigenproblems, several iterative algorithms exist. The publicly available library ARPACK (used in [DBG * 06]) provides an efficient implementation of the Arnoldi method. Yet, two characteristics of eigenproblem solvers hinder us from using them directly to compute the MHB for surfaces with more than a few thousand vertices:

• first of all, we are interested in the lower frequencies, i.e. eigenvectors with associated eigenvalues lower than ω 2 m . Unfortunately, iterative solvers perform much better for the other end of the spectrum. This can be explained in terms of filtering as lower frequencies correspond to higher powers of the smoothing kernel, which may have a poor condition number;

• secondly, we need to compute a large number of eigenvectors (typically a thousand), and it is well known that computation time is superlinear in the number of requested eigenvectors. In addition, if the surface is large (a million vertices), the MHB does not fit in system RAM.

Band-by-band computation of the MHB

We address both issues by applying spectral transforms to the eigenproblem. To get the eigenvectors of a spectral band centered around a value λ S , we start by shifting the spectrum by λ S , by replacing ∆ with ∆ S = ∆λ S Id. Then, we can swap the spectrum by inverting ∆ S . This is called the Shift-Invert spectral transform, and the new eigenproblem to solve is given by:

∆ -1 S Hk = µ k Hk ( 10
)
The fact that ∆ S may be singular is in practice not a problem as the iterative solver we use to solve (10) does not ask for ∆ -1 S explicitly. Instead, it outputs some vectors v and asks in return for the result of the multiplication x = ∆ -1 S v. Hence we only need to compute a sparse indefinite Cholevsy factorization of ∆ S using sparse direct solvers (TAUCS, SU-PERLU). Thanks to this factorization, it is very fast to solve ∆ S x = v by simple back-substitution each time the iterative solver asks for a multiplication with ∆ -1 S . For large models (a million vertices), we used the sparse OOC (out-of-core) symmetric indefinite factorization [START_REF] Meshar | An outof-core sparse symmetric indefinite factorization method[END_REF] implemented in the future release of TAUCS, kindly provided by S. Toledo.

It is easy to check that (9) and (10) yield the same eigenvectors, and that the eigenvalues are related by λ k = λ S + 1/µ k . Our iterative solver returns the high end of the spectrum (largest µ's), corresponding to a band of eigenvalues of ∆ centered around λ S . It is then possible to split the MHB computation into multiple bands, and obtain a computation time that is linear in the number of computed eigenpairs. Based on the considerations above, we derive the following "bandby-band" algorithm:

(1)

λ S ← 0 ; λ last ← 0 (2) while(λ last < ω 2 m ) (3)
compute the Cholevsky factorization of ∆ S = ∆λ S Id (4) find the 50 first eigenpairs ( Hk , µ k ) of ∆ -1

S

(5)

for k = 1 to 50 (6) λ k ← λ S + 1/µ k (7) if (λ k > λ last ) write( Hk , λ k ) (8) end // f or (9) λ S ← max(λ k ) + 0.4(max(λ k ) -min(λ k )) (10) λ last ← max(λ k ) (11) end //while
If the MHB does not fit in RAM, the new eigenpairs of each band of can be stream-writen into a file (Line 7). Since the eigenvalues are centered around the shift λ S , the shift for the next band is given by the last computed eigenvalue plus slightly less than half the bandwidth to ensure that the bands overlap and that we are not missing any eigenvalue (Line 9). If the bands do not overlap, we recompute a larger band until they do. Note that this is different from the shift-invert spectral transform implemented by ARPACK, dedicated to iterative solvers. Ours makes use of the factorization of the matrix, resulting in much better performances.

Limited-memory MH Filtering

After computing the MHB (Section 4.1) the filtering algorithm (Section 3.2) allows for interactive spectral geometry processing. However, for large meshes, storing the MHB may be prohibitive. Fortunately, it is possible to compute the MHB and the filter all together (at the cost of loosing interactivity). In addition, computations can be reordered in a way that requires storing only one eigenvector at a time: In a certain sense, this algorithm replaces a given frequency in the mesh by its filtered version. Once again, this is made possible by the orthonormality of the MHB. In practice, the combined MHB+filtering algorithm is obtained by replacing line (7) of the MHB computation algorithm with line (3) of the algorithm above (instead of streaming the eigenpair to a file, we replace the corresponding frequency in the mesh). Interestingly, since our limited-memory algorithm changes a specific frequency in-place (i.e. without storing the MHB), it is possible to limit the computation of the MHB to the frequencies changed by the filter, by using the shift-invert spectral transform.

(1) x F ← x (2) for each eigenpair(H k , ω k ) (3) x F ← x F + (F(ω k ) -1) < x, H k > H k (where < x, H k >= xk = x T 0 H k ) (4)

Results, Discussion and Conclusions

We have experimented the OOC factorization combined with the streamed band-by-band eigenvectors algorithm for computing up to a thousand eigenvectors on a mesh with one million vertices. We have also implemented an OOC version of the MHT, filtering and inverse MHT, that reads one frequency band at a time and accumulates its contribution.

We have experimented our filtering method with objects of different sizes. The timings are reported in table 1. The last row (limited-memory version) uses a band-exaggeration filter that spans 1/4th of the object's spectrum. As can be seen, since we only compute the concerned eigenpairs, this results in better performances (as compared to summing MHB + MHT + MHT -1 rows). For smoothing purposes only, our method does not outperform local approaches. However, for filters that involve low frequencies, performances are better than Geofilter [START_REF] Rossignac | GeoFilter: Geometric Selection of Mesh Filter Parameters[END_REF], since this latter method needs to compute the inverse of a power of the Laplacian matrix, that is not sparse anymore for lower ends of the spectrum. For large models, e.g. the 1M vertices dragon (Figure 6), performance is still slow (1h). However, note that no other existing method would allow to reach and act on the lower-end of the spectrum (that corresponds to large geometric details).

Our MH-based filtering can be applied to objects of arbitrary topology. Figure 7 shows a low-pass filter used to remove high-frequency noise from a sphere and from a genus 4 object. The low-pass filter nearly preserves the symmetry of the sphere. Figure 8 and the video show how our method implements an interactive version of geofilter [START_REF] Rossignac | GeoFilter: Geometric Selection of Mesh Filter Parameters[END_REF]. In addition, since our filter explicitly implements the spectral transform, it does not introduce the shrinking effect usually encountered with existing ones.

Conclusions

In this paper, we have presented a method for filtering functions defined on manifolds. Our method and associated numerical solution mechanism may find applications in various contexts, e.g. segmentation, mesh watermarking or reconstruction. We have explained how a DEC framework allows to recover the symmetry of discrete Laplace operators and the orthogonality of its eigenvectors. We used this theoretical framework to define the Manifold harmonic transform and inverse. After precomputing the MHB, the resulting filter is interactive and does not encounter the shrinking effect obtained with classical schemes. On the practical side, we have overcome the current size limits of spectral geometry processing by several orders of magnitudes, by making it usable for meshes with up to 10 5 -10 6 vertices. With our limited-memory MH filtering algorithm, storage space is nolonger a limit. However, processing time for the MHB starts to be expensive (hours) beyond 10 6 vertices. This will be optimized in future works, by introducing multiresolution in our solution mechanism.

Another limitation of our method concerns objects with creases. It is well known that low-pass filters based on Fourier-like methods cannot preserve the creases. Using the eigenfunctions of an anisotropic version of the Laplace operator may improve the frequency localization of the creases and therefore better preserve them when filtering.

Our solver applied to the uniform Laplacian can be also used to implement an efficient version of Karni et. al.'s Spectral Mesh Compression [START_REF] Karni | Spectral compression of mesh geometry[END_REF]. Our method cannot be directly applied to mesh compression as we took particular care making our Laplacian geometry dependant. In this case, a purely combinatorial Laplacian is required as in Karni et. al.'s Spectral Mesh Compression [START_REF] Karni | Spectral compression of mesh geometry[END_REF]. Moreover, it turns out that because the MHB is not spatially localized, many MHT coefficients (several thousands) are required to accurately reconstruct the geometry, even with a geometry aware Laplacian (see Figure 4). Besides Karni's initial concern of reducing computation time, we think that partitioning also partially fixes the problem of spatial localization (this is also why JPEG uses small blocks instead of applying the DCT to the whole image) at the expense of losing continuity. This leads to forecast that defining Manifold Wavelets localized in both frequency and spatial domains [START_REF] Grinspun | CHARMS: a simple framework for adaptive simulation[END_REF] will be an exciting research avenue in the future.

•

  B: once the MHB is computed, transform the geometry into frequency space by computing the Manifold Harmonic Transform (MHT) of the geometry, that is to say three vectors of coefficients [ x1 , x2 , . . . xm ], [ ỹ1 , ỹ2 , . . . ỹm ], and [z 1 , z2 , . . . zm ].

Figure 1 :

 1 Figure 1: Processing pipeline of our method: A: Compute the Manifold Harmonic Basis (MHB) of the input triangulated mesh. B: Transform the geometry into frequency space by computing the Manifold Harmonic Transform (MHT). C: Apply the frequency space filter on the transformed geometry. D: Transform back into geometric space by computing the inverse MHT.

Figure 3 :

 3 Figure 3: Some functions of the Manifold Harmonic Basis (MHB). Note the similarity with the sine products used by the DCT.

Figure 4 :

 4 Figure 4: Reconstructions obtained with an increasing number of MH functions.

Figure 5 :

 5 Figure 5: Low-pass, enhancement and band-exaggeration filters. The filter can be changed by the user, the surface is updated interactively.

Figure 7 :

 7 Figure 7: Left: a sphere and a genus-4 model with random noise added. Right: the low-pass filtered result.

Figure 6 :

 6 Figure 6: The MHB computed on 1M vertices (XYZ dragon) and limited-memory MH-filtering (that does not store the MHB).

Figure 8 :

 8 Figure 8: Filtering Stanford's bunny. Results similar to geofilter are obtained, with the addition of interactivity, and without any shrinking effect.

Table 1 :

 1 Timings for the different phases of the algorithm.

	end for

c 2008 The Author(s) Journal compilation c 2008 The Eurographics Association and Blackwell Publishing Ltd.

c 2008 The Author(s) Journal compilation c 2008 The Eurographics Association and Blackwell Publishing Ltd.

The so-defined Laplacian ∆ apparently looses the symmetry of its continuous counterpart (∆ i j = ∆ ji ). This makes the c 2008 The Author(s) Journal compilation c 2008 The Eurographics Association and Blackwell Publishing Ltd.

Acknowledgments

We gratefully thank all the reviewers of this paper and especially the senior reviewer for helping us to enhance the quality of this paper. We wish to thank Matthias Zwicker for the suggestion of studying manifold learning, Ramsey Dyer for discussions about orthogonality, Sivan Toledo for providing us with his latest TAUCS package. We are also grateful to Michela Spagnulo for encouraging us to continue in this direction, and Michael Garland for discussions on the eigenfunctions. We thank Raphaelle Chaine and Remi Allegre for some of the mesh models. This work was funded by AIM@Shape (FP6 European Network of Excellence), ARC GEOREP (INRIA grant) and Geometric Intelligence (Microsoft Research grant).