---
_id: '60461'
abstract:
- lang: eng
  text: <jats:title>Abstract</jats:title><jats:p>Efficient methods to compute intrinsic
    distances and geodesic paths have been presented for various types of surface
    representations, most importantly polygon meshes. These meshes are usually assumed
    to be well‐structured and manifold. In practice, however, they often contain defects
    like holes, gaps, degeneracies, non‐manifold configurations – or they might even
    be just a soup of polygons. The task of repairing these defects is computationally
    complex and in many cases exhibits various ambiguities demanding tedious manual
    efforts. We present a computational framework that enables the computation of
    meaningful approximate intrinsic distances and geodesic paths on raw meshes in
    a way which is tolerant to such defects. Holes and gaps are bridged up to a user‐specified
    tolerance threshold such that distances can be computed plausibly even across
    multiple connected components of inconsistent meshes. Further, we show ways to
    locally parameterize a surface based on geodesic distance fields, easily facilitating
    the application of textures and decals on raw meshes. We do all this without explicitly
    repairing the input, thereby avoiding the costly additional efforts. In order
    to enable broad applicability we provide details on two implementation variants,
    one optimized for performance, the other optimized for memory efficiency. Using
    the presented framework many applications can readily be extended to deal with
    imperfect meshes. Since we abstract from the input applicability is not even limited
    to meshes, other representations can be handled as well.</jats:p>
author:
- first_name: Marcel
  full_name: Campen, Marcel
  id: '114904'
  last_name: Campen
  orcid: 0000-0003-2340-3462
- first_name: Leif
  full_name: Kobbelt, Leif
  last_name: Kobbelt
citation:
  ama: 'Campen M, Kobbelt L. Walking On Broken Mesh: Defect‐Tolerant Geodesic Distances
    and Parameterizations. <i>Computer Graphics Forum</i>. 2011;30(2):623-632. doi:<a
    href="https://doi.org/10.1111/j.1467-8659.2011.01896.x">10.1111/j.1467-8659.2011.01896.x</a>'
  apa: 'Campen, M., &#38; Kobbelt, L. (2011). Walking On Broken Mesh: Defect‐Tolerant
    Geodesic Distances and Parameterizations. <i>Computer Graphics Forum</i>, <i>30</i>(2),
    623–632. <a href="https://doi.org/10.1111/j.1467-8659.2011.01896.x">https://doi.org/10.1111/j.1467-8659.2011.01896.x</a>'
  bibtex: '@article{Campen_Kobbelt_2011, title={Walking On Broken Mesh: Defect‐Tolerant
    Geodesic Distances and Parameterizations}, volume={30}, DOI={<a href="https://doi.org/10.1111/j.1467-8659.2011.01896.x">10.1111/j.1467-8659.2011.01896.x</a>},
    number={2}, journal={Computer Graphics Forum}, publisher={Wiley}, author={Campen,
    Marcel and Kobbelt, Leif}, year={2011}, pages={623–632} }'
  chicago: 'Campen, Marcel, and Leif Kobbelt. “Walking On Broken Mesh: Defect‐Tolerant
    Geodesic Distances and Parameterizations.” <i>Computer Graphics Forum</i> 30,
    no. 2 (2011): 623–32. <a href="https://doi.org/10.1111/j.1467-8659.2011.01896.x">https://doi.org/10.1111/j.1467-8659.2011.01896.x</a>.'
  ieee: 'M. Campen and L. Kobbelt, “Walking On Broken Mesh: Defect‐Tolerant Geodesic
    Distances and Parameterizations,” <i>Computer Graphics Forum</i>, vol. 30, no.
    2, pp. 623–632, 2011, doi: <a href="https://doi.org/10.1111/j.1467-8659.2011.01896.x">10.1111/j.1467-8659.2011.01896.x</a>.'
  mla: 'Campen, Marcel, and Leif Kobbelt. “Walking On Broken Mesh: Defect‐Tolerant
    Geodesic Distances and Parameterizations.” <i>Computer Graphics Forum</i>, vol.
    30, no. 2, Wiley, 2011, pp. 623–32, doi:<a href="https://doi.org/10.1111/j.1467-8659.2011.01896.x">10.1111/j.1467-8659.2011.01896.x</a>.'
  short: M. Campen, L. Kobbelt, Computer Graphics Forum 30 (2011) 623–632.
date_created: 2025-06-30T08:14:56Z
date_updated: 2025-07-14T12:35:50Z
department:
- _id: '969'
doi: 10.1111/j.1467-8659.2011.01896.x
extern: '1'
intvolume: '        30'
issue: '2'
language:
- iso: eng
page: 623-632
publication: Computer Graphics Forum
publication_identifier:
  issn:
  - 0167-7055
  - 1467-8659
publication_status: published
publisher: Wiley
status: public
title: 'Walking On Broken Mesh: Defect‐Tolerant Geodesic Distances and Parameterizations'
type: journal_article
user_id: '117512'
volume: 30
year: '2011'
...
---
_id: '60463'
abstract:
- lang: eng
  text: <jats:title>Abstract</jats:title><jats:p>We present a new technique to implement
    operators that modify the topology of polygonal meshes at intersections and self‐intersections.
    Depending on the modification strategy, this effectively results in operators
    for Boolean combinations or for the construction of outer hulls that are suited
    for mesh repair tasks and accurate mesh‐based front tracking of deformable materials
    that split and merge. By combining an adaptive octree with nested binary space
    partitions (BSP), we can guarantee exactness (= correctness) and robustness (=
    completeness) of the algorithm while still achieving higher performance and less
    memory consumption than previous approaches. The efficiency and scalability in
    terms of runtime and memory is obtained by an operation localization scheme. We
    restrict the essential computations to those cells in the adaptive octree where
    intersections actually occur. Within those critical cells, we convert the input
    geometry into a plane‐based BSP‐representation which allows us to perform all
    computations exactly even with fixed precision arithmetics. We carefully analyze
    the precision requirements of the involved geometric data and predicates in order
    to guarantee correctness and show how minimal input mesh quantization can be used
    to safely rely on computations with standard floating point numbers. We properly
    evaluate our method with respect to precision, robustness, and efficiency.</jats:p>
author:
- first_name: Marcel
  full_name: Campen, Marcel
  id: '114904'
  last_name: Campen
  orcid: 0000-0003-2340-3462
- first_name: Leif
  full_name: Kobbelt, Leif
  last_name: Kobbelt
citation:
  ama: Campen M, Kobbelt L. Exact and Robust (Self‐)Intersections for Polygonal Meshes.
    <i>Computer Graphics Forum</i>. 2010;29(2):397-406. doi:<a href="https://doi.org/10.1111/j.1467-8659.2009.01609.x">10.1111/j.1467-8659.2009.01609.x</a>
  apa: Campen, M., &#38; Kobbelt, L. (2010). Exact and Robust (Self‐)Intersections
    for Polygonal Meshes. <i>Computer Graphics Forum</i>, <i>29</i>(2), 397–406. <a
    href="https://doi.org/10.1111/j.1467-8659.2009.01609.x">https://doi.org/10.1111/j.1467-8659.2009.01609.x</a>
  bibtex: '@article{Campen_Kobbelt_2010, title={Exact and Robust (Self‐)Intersections
    for Polygonal Meshes}, volume={29}, DOI={<a href="https://doi.org/10.1111/j.1467-8659.2009.01609.x">10.1111/j.1467-8659.2009.01609.x</a>},
    number={2}, journal={Computer Graphics Forum}, publisher={Wiley}, author={Campen,
    Marcel and Kobbelt, Leif}, year={2010}, pages={397–406} }'
  chicago: 'Campen, Marcel, and Leif Kobbelt. “Exact and Robust (Self‐)Intersections
    for Polygonal Meshes.” <i>Computer Graphics Forum</i> 29, no. 2 (2010): 397–406.
    <a href="https://doi.org/10.1111/j.1467-8659.2009.01609.x">https://doi.org/10.1111/j.1467-8659.2009.01609.x</a>.'
  ieee: 'M. Campen and L. Kobbelt, “Exact and Robust (Self‐)Intersections for Polygonal
    Meshes,” <i>Computer Graphics Forum</i>, vol. 29, no. 2, pp. 397–406, 2010, doi:
    <a href="https://doi.org/10.1111/j.1467-8659.2009.01609.x">10.1111/j.1467-8659.2009.01609.x</a>.'
  mla: Campen, Marcel, and Leif Kobbelt. “Exact and Robust (Self‐)Intersections for
    Polygonal Meshes.” <i>Computer Graphics Forum</i>, vol. 29, no. 2, Wiley, 2010,
    pp. 397–406, doi:<a href="https://doi.org/10.1111/j.1467-8659.2009.01609.x">10.1111/j.1467-8659.2009.01609.x</a>.
  short: M. Campen, L. Kobbelt, Computer Graphics Forum 29 (2010) 397–406.
date_created: 2025-06-30T08:24:08Z
date_updated: 2025-07-14T12:35:44Z
department:
- _id: '969'
doi: 10.1111/j.1467-8659.2009.01609.x
extern: '1'
intvolume: '        29'
issue: '2'
language:
- iso: eng
page: 397-406
publication: Computer Graphics Forum
publication_identifier:
  issn:
  - 0167-7055
  - 1467-8659
publication_status: published
publisher: Wiley
status: public
title: Exact and Robust (Self‐)Intersections for Polygonal Meshes
type: journal_article
user_id: '117512'
volume: 29
year: '2010'
...
---
_id: '60464'
abstract:
- lang: eng
  text: <jats:title>Abstract</jats:title><jats:p>We present a novel technique for
    the efficient boundary evaluation of sweep operations applied to objects in polygonal
    boundary representation. These sweep operations include Minkowski addition, offsetting,
    and sweeping along a discrete rigid motion trajectory. Many previous methods focus
    on the construction of a polygonal superset (containing self‐intersections and
    spurious internal geometry) of the boundary of the volumes which are swept. Only
    few are able to determine a clean representation of the actual boundary, most
    of them in a discrete volumetric setting. We unify such superset constructions
    into a succinct common formulation and present a technique for the robust extraction
    of a polygonal mesh representing the outer boundary, i.e. it makes no general
    position assumptions and always yields a manifold, watertight mesh. It is exact
    for Minkowski sums and approximates swept volumes polygonally. By using plane‐based
    geometry in conjunction with hierarchical arrangement computations we avoid the
    necessity of arbitrary precision arithmetics and extensive special case handling.
    By restricting operations to regions containing pieces of the boundary, we significantly
    enhance the performance of the algorithm.</jats:p>
author:
- first_name: Marcel
  full_name: Campen, Marcel
  id: '114904'
  last_name: Campen
  orcid: 0000-0003-2340-3462
- first_name: Leif
  full_name: Kobbelt, Leif
  last_name: Kobbelt
citation:
  ama: Campen M, Kobbelt L. Polygonal Boundary Evaluation of Minkowski Sums and Swept
    Volumes. <i>Computer Graphics Forum</i>. 2010;29(5):1613-1622. doi:<a href="https://doi.org/10.1111/j.1467-8659.2010.01770.x">10.1111/j.1467-8659.2010.01770.x</a>
  apa: Campen, M., &#38; Kobbelt, L. (2010). Polygonal Boundary Evaluation of Minkowski
    Sums and Swept Volumes. <i>Computer Graphics Forum</i>, <i>29</i>(5), 1613–1622.
    <a href="https://doi.org/10.1111/j.1467-8659.2010.01770.x">https://doi.org/10.1111/j.1467-8659.2010.01770.x</a>
  bibtex: '@article{Campen_Kobbelt_2010, title={Polygonal Boundary Evaluation of Minkowski
    Sums and Swept Volumes}, volume={29}, DOI={<a href="https://doi.org/10.1111/j.1467-8659.2010.01770.x">10.1111/j.1467-8659.2010.01770.x</a>},
    number={5}, journal={Computer Graphics Forum}, publisher={Wiley}, author={Campen,
    Marcel and Kobbelt, Leif}, year={2010}, pages={1613–1622} }'
  chicago: 'Campen, Marcel, and Leif Kobbelt. “Polygonal Boundary Evaluation of Minkowski
    Sums and Swept Volumes.” <i>Computer Graphics Forum</i> 29, no. 5 (2010): 1613–22.
    <a href="https://doi.org/10.1111/j.1467-8659.2010.01770.x">https://doi.org/10.1111/j.1467-8659.2010.01770.x</a>.'
  ieee: 'M. Campen and L. Kobbelt, “Polygonal Boundary Evaluation of Minkowski Sums
    and Swept Volumes,” <i>Computer Graphics Forum</i>, vol. 29, no. 5, pp. 1613–1622,
    2010, doi: <a href="https://doi.org/10.1111/j.1467-8659.2010.01770.x">10.1111/j.1467-8659.2010.01770.x</a>.'
  mla: Campen, Marcel, and Leif Kobbelt. “Polygonal Boundary Evaluation of Minkowski
    Sums and Swept Volumes.” <i>Computer Graphics Forum</i>, vol. 29, no. 5, Wiley,
    2010, pp. 1613–22, doi:<a href="https://doi.org/10.1111/j.1467-8659.2010.01770.x">10.1111/j.1467-8659.2010.01770.x</a>.
  short: M. Campen, L. Kobbelt, Computer Graphics Forum 29 (2010) 1613–1622.
date_created: 2025-06-30T08:34:20Z
date_updated: 2025-07-14T12:35:40Z
department:
- _id: '969'
doi: 10.1111/j.1467-8659.2010.01770.x
extern: '1'
intvolume: '        29'
issue: '5'
language:
- iso: eng
page: 1613-1622
publication: Computer Graphics Forum
publication_identifier:
  issn:
  - 0167-7055
  - 1467-8659
publication_status: published
publisher: Wiley
status: public
title: Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes
type: journal_article
user_id: '117512'
volume: 29
year: '2010'
...
---
_id: '60462'
abstract:
- lang: eng
  text: '<jats:title>Abstract</jats:title><jats:p> <jats:italic>In this paper, we
    present a novel method to compute Boolean operations on polygonal meshes. Given
    a Boolean expression over an arbitrary number of input meshes we reliably and
    efficiently compute an output mesh which faithfully preserves the existing sharp
    features and precisely reconstructs the new features appearing along the intersections
    of the input meshes. The term “hybrid” applies to our method in two ways: First,
    our algorithm operates on a hybrid data structure which stores the original input
    polygons (surface data) in an adaptively refined octree (volume data). By this
    we combine the robustness of volumetric techniques with the accuracy of surface‐oriented
    techniques. Second, we generate a new triangulation only in a close vicinity around
    the intersections of the input meshes and thus preserve as much of the original
    mesh structure as possible (hybrid mesh). Since the actual processing of the Boolean
    operation is confined to a very small region around the intersections of the input
    meshes, we can achieve very high adaptive refinement resolutions and hence very
    high precision. We demonstrate our method on a number of challenging examples.</jats:italic>
    </jats:p>'
author:
- first_name: Darko
  full_name: Pavić, Darko
  last_name: Pavić
- first_name: Marcel
  full_name: Campen, Marcel
  id: '114904'
  last_name: Campen
  orcid: 0000-0003-2340-3462
- first_name: Leif
  full_name: Kobbelt, Leif
  last_name: Kobbelt
citation:
  ama: Pavić D, Campen M, Kobbelt L. Hybrid Booleans. <i>Computer Graphics Forum</i>.
    2010;29(1):75-87. doi:<a href="https://doi.org/10.1111/j.1467-8659.2009.01545.x">10.1111/j.1467-8659.2009.01545.x</a>
  apa: Pavić, D., Campen, M., &#38; Kobbelt, L. (2010). Hybrid Booleans. <i>Computer
    Graphics Forum</i>, <i>29</i>(1), 75–87. <a href="https://doi.org/10.1111/j.1467-8659.2009.01545.x">https://doi.org/10.1111/j.1467-8659.2009.01545.x</a>
  bibtex: '@article{Pavić_Campen_Kobbelt_2010, title={Hybrid Booleans}, volume={29},
    DOI={<a href="https://doi.org/10.1111/j.1467-8659.2009.01545.x">10.1111/j.1467-8659.2009.01545.x</a>},
    number={1}, journal={Computer Graphics Forum}, publisher={Wiley}, author={Pavić,
    Darko and Campen, Marcel and Kobbelt, Leif}, year={2010}, pages={75–87} }'
  chicago: 'Pavić, Darko, Marcel Campen, and Leif Kobbelt. “Hybrid Booleans.” <i>Computer
    Graphics Forum</i> 29, no. 1 (2010): 75–87. <a href="https://doi.org/10.1111/j.1467-8659.2009.01545.x">https://doi.org/10.1111/j.1467-8659.2009.01545.x</a>.'
  ieee: 'D. Pavić, M. Campen, and L. Kobbelt, “Hybrid Booleans,” <i>Computer Graphics
    Forum</i>, vol. 29, no. 1, pp. 75–87, 2010, doi: <a href="https://doi.org/10.1111/j.1467-8659.2009.01545.x">10.1111/j.1467-8659.2009.01545.x</a>.'
  mla: Pavić, Darko, et al. “Hybrid Booleans.” <i>Computer Graphics Forum</i>, vol.
    29, no. 1, Wiley, 2010, pp. 75–87, doi:<a href="https://doi.org/10.1111/j.1467-8659.2009.01545.x">10.1111/j.1467-8659.2009.01545.x</a>.
  short: D. Pavić, M. Campen, L. Kobbelt, Computer Graphics Forum 29 (2010) 75–87.
date_created: 2025-06-30T08:22:33Z
date_updated: 2025-07-14T12:35:48Z
department:
- _id: '969'
doi: 10.1111/j.1467-8659.2009.01545.x
extern: '1'
intvolume: '        29'
issue: '1'
language:
- iso: eng
page: 75-87
publication: Computer Graphics Forum
publication_identifier:
  issn:
  - 0167-7055
  - 1467-8659
publication_status: published
publisher: Wiley
status: public
title: Hybrid Booleans
type: journal_article
user_id: '117512'
volume: 29
year: '2010'
...