---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '22241'
abstract:
- lang: eng
  text: We revisit the computation of 3D generalized winding numbers, a useful measure
    for inside-outside classification on triangle meshes with gaps, self-intersections,
    and open boundaries. At the core of our new method is an analytical reduction
    of the surface integral that defines the winding number, resulting in a single
    ray-mesh intersection test and an elementary sum over boundary edges per evaluation.
    This construction is orders of magnitude more efficient than the state of the
    art in practice, which we show in an extensive performance benchmark. Conveniently,
    the method also reduces to the best-available asymptotic complexity in the worst
    case, and it introduces no approximations apart from floating-point errors. Our
    algorithm is conceptually simple to understand, straightforward to implement and
    debug, and it works reliably even on extremely noisy and corrupt input geometry.
acknowledgement: "We thank Sadashige Ishida and Ryusuke Sugimoto for their insightful
  discussions and proofreading and other members of the ISTA\r\nVisual Computing Group
  for their general feedback. This project was\r\nfunded in part by the European Research
  Council (ERC Consolidator\r\nGrant 101045083 CoDiNA)."
article_number: '41'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Peiyuan
  full_name: Xie, Peiyuan
  id: 488e236c-6bad-11f0-9831-859175c78e8a
  last_name: Xie
- first_name: Christian
  full_name: Hafner, Christian
  id: 400429CC-F248-11E8-B48F-1D18A9856A87
  last_name: Hafner
- first_name: Christopher J
  full_name: Wojtan, Christopher J
  id: 3C61F1D2-F248-11E8-B48F-1D18A9856A87
  last_name: Wojtan
  orcid: 0000-0001-6646-5546
citation:
  ama: Xie P, Hafner C, Wojtan C. Fast and exact winding numbers for triangle meshes.
    <i>ACM Transactions on Graphics</i>. 2026;45(4). doi:<a href="https://doi.org/10.1145/3811339">10.1145/3811339</a>
  apa: Xie, P., Hafner, C., &#38; Wojtan, C. (2026). Fast and exact winding numbers
    for triangle meshes. <i>ACM Transactions on Graphics</i>. Association for Computing
    Machinery. <a href="https://doi.org/10.1145/3811339">https://doi.org/10.1145/3811339</a>
  chicago: Xie, Peiyuan, Christian Hafner, and Chris Wojtan. “Fast and Exact Winding
    Numbers for Triangle Meshes.” <i>ACM Transactions on Graphics</i>. Association
    for Computing Machinery, 2026. <a href="https://doi.org/10.1145/3811339">https://doi.org/10.1145/3811339</a>.
  ieee: P. Xie, C. Hafner, and C. Wojtan, “Fast and exact winding numbers for triangle
    meshes,” <i>ACM Transactions on Graphics</i>, vol. 45, no. 4. Association for
    Computing Machinery, 2026.
  ista: Xie P, Hafner C, Wojtan C. 2026. Fast and exact winding numbers for triangle
    meshes. ACM Transactions on Graphics. 45(4), 41.
  mla: Xie, Peiyuan, et al. “Fast and Exact Winding Numbers for Triangle Meshes.”
    <i>ACM Transactions on Graphics</i>, vol. 45, no. 4, 41, Association for Computing
    Machinery, 2026, doi:<a href="https://doi.org/10.1145/3811339">10.1145/3811339</a>.
  short: P. Xie, C. Hafner, C. Wojtan, ACM Transactions on Graphics 45 (2026).
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-03T21:03:48Z
date_published: 2026-07-03T00:00:00Z
date_updated: 2026-07-06T06:14:18Z
day: '03'
ddc:
- '000'
department:
- _id: GradSch
- _id: ChWo
doi: 10.1145/3811339
file:
- access_level: open_access
  checksum: 7e36e69f377b680a893e65b620b43813
  content_type: application/pdf
  creator: dernst
  date_created: 2026-07-06T06:13:12Z
  date_updated: 2026-07-06T06:13:12Z
  file_id: '22249'
  file_name: 2026_TransactionsGraphics_Xie.pdf
  file_size: 5212838
  relation: main_file
  success: 1
file_date_updated: 2026-07-06T06:13:12Z
has_accepted_license: '1'
intvolume: '        45'
issue: '4'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: 34bc2376-11ca-11ed-8bc3-9a3b3961a088
  grant_number: '101045083'
  name: Computational Discovery of Numerical Algorithms for Animation and Simulation
    of Natural Phenomena
publication: ACM Transactions on Graphics
publication_identifier:
  eissn:
  - 1557-7368
  issn:
  - 0730-0301
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Fast and exact winding numbers for triangle meshes
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 45
year: '2026'
...