Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Rigid Body Dynamics and Conformal Geometric Algebra Read chapter Read first chapter

2011 | OriginalPaper | Chapter

14. A Framework for n-Dimensional Visibility Computations

Authors : Lilian Aveneau, Sylvain Charneau, Laurent Fuchs, Frederic Mora

Published in: Guide to Geometric Algebra in Practice

Publisher: Springer London

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This chapter introduces global visibility computation using Grassmann Algebra. Visibility computation is a fundamental task in computer graphics, as in many other scientific domains. While it is well understood in two dimensions, this does not remain true in higher-dimensional spaces.
Grassmann Algebra allows to think about visibility at a high level of abstraction and to design a framework for solving visibility problems in any n-dimensional space for n≥2. Contrary to Stolfi’s framework which allows only the representation of geometric lines, its algebraic nature deals means general applicability, with no exceptional cases.
This chapter shows how the space of lines can be defined as a projective space over the bivector vector space. Then line classification, a key point for the visibility computation, is achieved using the exterior product. Actually, line classification turns out to be equivalent to point vs. hyperplane classification relative to a nondegenerate bilinear form. This ensures it is well defined and computationally robust.
Using this, the lines stabbing an n-dimensional convex face are characterized. This set of lines appears to be the intersection of the decomposable bivectors set (i.e., bivectors that represent a line) and a convex polytope. Moreover, this convex polytope is proved to be minimal. This property allows useful algorithmic improvements.
To illustrate the use of our framework in practice, we present the computation of soft shadows for three-dimensional illuminated scenes.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Line Geometry in Terms of the Null Geometric Algebra over ℝ3,3, and Application to the Inverse Singularity Analysis of Generalized Stewart Platforms
next chapter On the Homogeneous Model of Euclidean Geometry
Footnotes
1
Editorial note: The δ is a dualization in \(\bigwedge({\mathbb{R}}^{n+1})\). If one would have a geometric algebra for ℝ n+1, this would be proportional to multiplication by the pseudoscalar, see Chap. 21 and their 2D example below. In a nonmetric Grassmann algebra, the dualization is necessarily introduced somewhat more abstractly.
 
2
Using homogeneous coordinates, the sum of the coefficients does not need to be normalized to unity, as it is usually done in computational geometry.
 
Literature
1.
2.
Bajaj, C.L., Pascucci, V.: Splitting a complex of convex polytopes in any dimension. In: Proceedings of the Twelfth Annual Symposium on Computational Geometry (ISG ’96), pp. 88–97, ACM, New York (1996) CrossRef
3.
Bittner, J.: Hierarchical techniques for visibility computation. PhD thesis, Department of Computer Science and Engineering, Czech Technical University in Prague (2002)
4.
Bittner, J., Prikryl, J., Slavík, P.: Exact regional visibility using line space partitioning. Comput. Graph. 27(4), 569–580 (2003) CrossRef
5.
Dorst, L., Fontijne, D., Mann, S.: Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry. The Morgan Kaufmann Series in Computer Graphics. Morgan Kaufmann, San Francisco (2007)
6.
Durand, F., Drettakis, G., Puech, C.: The visibility skeleton: a powerful and efficient multi-purpose global visibility tool. In: Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’97, pp. 89–100 (1997) CrossRef
7.
Durand, F., Drettakis, G., Puech, C.: The 3d visibility complex. ACM Trans. Graph. 21, 176–206 (2002) CrossRef
8.
Haumont, D., Makinen, O., Nirenstein, S.: A low dimensional framework for exact polygon-to-polygon occlusion queries. In: Rendering Techniques, pp. 211–222 (2005)
9.
Möller, T., Trumbore, B.: Fast minimum storage ray–triangle intersection. J. Graph. GPU Game Tools 2(1), 21–28 (1997)
10.
Mora, F., Aveneau, L.: Fast exact direct illumination. In: Proceedings of the Computer Graphics International 2005, pp. 191–197 (2005) CrossRef
11.
Mora, F., Aveneau, L., Mériaux, M.: Coherent exact polygon-to-polygon visibility. In: WSCG’05, pp. 87–94 (2005)
12.
Naylor, B.F., Amanatides, J., Thibault, W.C.: Merging BSP trees yields polyhedral set operations. In: SIGGRAPH, pp. 115–124 (1990)
13.
Nirenstein, S., Blake, E.H., Gain, J.E.: Exact from-region visibility culling. In: Rendering Techniques, pp. 191–202 (2002)
14.
Orti, R., Durand, F., Rivière, S., Puech, C.: Using the visibility complex for radiosity computation. In: WACG, pp. 177–190 (1996)
15.
Pellegrini, M.: Ray shooting and lines in space. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., pp. 839–856. Chapman & Hall/CRC Press, Boca Raton (2004)
16.
17.
Stolfi, J.: Oriented Projective Geometry: A Framework for Geometric Computations. Academic Press, San Diego (1991) MATH
18.
Teller, S.J.: Computing the antipenumbra of an area light source. In: Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’92, pp. 139–148. ACM, New York (1992) CrossRef
19.
Teller, S.J., Séquin, C.H.: Visibility preprocessing for interactive walkthroughs. In: Proceedings of the 18th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’91, pp. 61–70. ACM, New York (1991) CrossRef
20.
Wald, I., Slusallek, P., Benthin, C., Wagner, M.: Interactive rendering with coherent ray tracing. Comput. Graph. Forum 20(3), 153–164 (2001) CrossRef
Metadata
Title
A Framework for n-Dimensional Visibility Computations
Authors
Lilian Aveneau
Sylvain Charneau
Laurent Fuchs
Frederic Mora
Copyright Year
2011
Publisher
Springer London
Book
Guide to Geometric Algebra in Practice

Print ISBN: 978-0-85729-810-2

Electronic ISBN: 978-0-85729-811-9

Copyright Year: 2011

DOI
https://doi.org/10.1007/978-0-85729-811-9_14

Premium Partner

    Image Credits