Christopher Dyken, PhD

E-mail: LinkedIn profile SINTEF profile

Software HPMC, a small GPL library for iso-surface extraction using OpenGL. Teaching INF3320/INF4320 Computer Graphics and Geometric Modelling. Teaching: 2007, 2006, 2005, 2004, Tutoring: 2003. Supervision of students Current students: Martin Lilleeng Sætra (PhD fellow) Past students: Erik W. Bjønnes (MSc) Publications A. R. Brodtkorb, C. Dyken, T. R. Hagen, J. M. Hjelmervik, O. O. Storaasli, State-of-the-Art in Heterogeneous Computing, Journal of Scientific Programming, to appear. Node level heterogeneous architectures have become attractive during the last decade for several reasons: compared to traditional symmetric CPUs, they offer high peak performance and are energy and/or cost efficient. With the increase of fine-grained parallelism in high-performance computing, as well as the introduction of parallelism in workstations, there is an acute need for a good overview and understanding of these architectures. We give an overview of the state-of-the-art in heterogeneous computing, focusing on three commonly found architectures: the Cell Broadband Engine Architecture, graphics processing units (GPUs), and field programmable gate arrays (FPGAs). We give a review of hardware, available software tools, and an overview of state-of-the-art techniques and algorithms. We further present a qualitative and quantitative comparison of the architectures, and give our view on the future of heterogeneous computing. Early draft C. Dyken, M. Dæhlen, T. Sevaldrud, Simultaneous Curve Simplification, Journal of Geographical Systems 11 (3), 2009, pp. 273-289. In this paper we present a method for simultaneous simplification of a collection of piecewise linear curves in the plane. The method is based on triangulations, and the main purpose is to remove line segments from the piecewise linear curves without changing the topological relations between the curves. The method can also be used to construct a multi-level representation of a collection of piecewise linear curves. We illustrate the method by simplifying cartographic contours and a set of piecewise linear curves representing a road network. C. Dyken, M. Reimers, J. Seland, Semi-uniform Adaptive Patch Tessellation, Computer Graphics Forum, 28(8), 2009, pp. 2255-2263. We present an adaptive tessellation scheme for surfaces consisting of parametric patches. The resulting tessellations are topologically uniform, yet consistent and watertight across boundaries of patches with different tessellation levels. Our scheme is simple to implement, requires little memory, and is well suited for instancing, a feature available on current GPUs that allows a substantial performance increase. We describe how the scheme can be implemented efficiently and give performance benchmarks comparing it to some other approaches. Early draft Implementations: Our developement code (source libdyk, gpu_refine), NVIDIA D3D SDK 10 Media: video, debug-gfx desc. C. Dyken, Topics in mesh-based modelling and computer graphics Philosophiae Doctor (Ph.D.) thesis, IfI, UiO, 2008. Compilation of the papers "Transfinite mean value interpolation", "Preferred directions for resolving the non-uniqueness of Delaunay triangulations", "Simultaneous curve simplification", "Real-time linear silhouette enhancement", "Real-time GPU silhouette refinement using adaptively blended Bezier patches", "Semi-uniform adaptive patch tessellation", and "High-speed marching cubes using histogram pyramids". With introduction. Press release (in Norwegian): Erik Christopher Dyken har levert en avhandling bestående av en samling vitenskapelige artikler som omhandler sider ved konstruksjon, håndtering og visualisering av digitale geometriske modeller. I dataspill er det en utfordring å lage realistiske geometriske modeller uten å øke datamengden så mye at modellene blir uhåndterlige. En vanlig strategi er å bruke en grov modell og så øke den visuelle detaljrikdommen ved å "lime" digitale bilder på modellen. Siden dette ikke endrer den faktiske geometrien til modellen, og siluetten er direkte gitt av geometrien, forblir siluettlinjene grove og kantete. Synet bruker siluetter for å oppfatte objekter, så kantete siluetter har en tendens til å bli ganske fremtredende. I artiklene blir en metode presentert som finner områder i naerheten av siluettlinjene for så sømløst å bytte ut den grove geometrien i disse områdene med en finere geometri, som gir glattere og penere siluetter. En litt beslektet problemstilling som også blir behandlet er forenkling av kartdata. Siden kartdata ofte er veldig store og detaljerte er forenkling aktuelt for blandt annet mobile karttjenester, hvor det er begrensninger i overførings og lagringskapasitet. En utfordring er at hvis man, for eksempel, forenkler en kronglete vei med en rett linje kan man risikere at den rette linjen går oppå en nabovei og følgelig introduserer veikryss som ikke eksisterer. Kjernen i metoden som er utviklet er å forenkle kartdata konsistent, det vil si at ingen nye kryss blir introdusert, ingen kryss forsvinner og veier forblir p&aslash; samme side av hverandre. Innen medisin og seismikk håndterer man ofte store tredimensjonale datasett, og man er mange ganger interessert i å trekke ut overflaten til et område som har spesielle karakteristika, for eksempel en lever eller nyre fra medisinske data eller en lomme med olje fra seismiske data. Ofte skal disse overflatene tegnes på skjermen og en av artiklene presenterer en metode som lar grafikkortet trekke ut overflaten direkte fra datasettet på egen hånd, en strategi som er effektiv fordi et moderne grafikkort har mange ganger så stor regnekapasiteten som hovedprosessoren. I den mer teoretiske enden ligger arbeidet med transfinitt interpolasjon, det vil si problemet med å finne en flate som går gjennom et sett av høydekurver, og en av artiklene tar for seg en metode for å løse slike problemer. Det blir bevist at metoden garantert fungerer under relativt svake betingelser, samt at metoden blir utvidet til å håndtere problemer hvor brattheten til flaten på tvers av høydekurvene er kjent. BibTeX entry, Final version, Presentation slides, Trial lecture C. Dyken, G. Ziegler, C. Theobalt, H.-P. Seidel, High-speed Marching Cubes using Histogram Pyramids, Computer Graphics Forum 27 (8), 2008, pp. 2028-2039. We present an implementation approach for Marching Cubes on graphics hardware for OpenGL 2.0 or comparable APIs. It currently outperforms all other known GPU-based iso-surface extraction algorithms in direct rendering for sparse or large volumes, even those using the recently introduced geometry shader capabilites. To achieve this, we outfit the HistoPyramid algorithm, previously only used in GPU data compaction, with the capability for arbitrary data expansion. After reformulation of Marching Cubes as a data compaction and expansion process, the HistoPyramid algorithm becomes the core of a highly efficient and interactive Marching Cube implementation. For graphics hardware lacking geometry shaders, such as mobile GPUs, the concept of HistoPyramid data expansion is easily generalized, opening new application domains in mobile visual computing. Further, to serve recent developments, we present how the HistoPyramid can be implemented in the parallel programming language CUDA, by using a novel 1D chunk/layer construction. Paper: early draft, MPI techreport Implementations: HPMC open source library. Our development code (source libdyk, gpu_marcher) Media: metaballs video, algebraic morph video Discussion: thread on gpgpu.org. C. Dyken, M. S. Floater, Transfinite mean value interpolation, Computer Aided Geometric Design 26, 2009, pp. 117-134. Transfinite mean value interpolation has recently emerged as a simple and robust way to interpolate a function f defined on the boundary of a planar domain. In this paper we study basic properties of the interpolant, including sufficient conditions on the boundary of the domain to guarantee interpolation when f is continuous. Then, by deriving the normal derivative of the interpolant and of a mean value weight function, we construct a transfinite Hermite interpolant and discuss various applications. Paper: early draft. C. Dyken, M. Reimers, J. Seland, Real-Time GPU Silhouette Refinement using adaptively blended Bezier Patches, Computer Graphics Forum 27 (1), 2008, pp. 1-12. We present an algorithm for detecting and extracting the silhouette edges of a triangle mesh in real time using GPUs (Graphical Processing Units). We also propose a tessellation strategy for visualizing the mesh with smooth silhouettes through a continuous blend between Bézier patches with varying level of detail. Furthermore, we show how our techniques can be integrated with displacement and normal mapping. We give details on our GPU implementation and provide a performance analysis with respect to mesh size. Paper: final version, early draft Media: old demo video. C. Dyken, M. S. Floater, Preferred directions for resolving the non-uniqueness of Delaunay triangulations, Computational Geometry: Theory and Applications 43, 2006, pp. 96-101. This note proposes a simple rule to determine a unique triangulation among all Delaunay triangulations of a planar point set, based on two preferred directions. We show that the triangulation can be generated by extending Lawson's edge-swapping algorithm and that point deletion is a local procedure. The rule can be implemented exactly when the points have integer coordinates and can be used to improve image compression methods. Paper: early draft C. Dyken, M. Reimers, Real-time Linear Silhouette Enhancement, Mathematical Methods for Curves and Surfaces: Tromsø 2004, M. Dæhlen, K. Mørken, and L. L. Schumaker (eds.), 2005, pp. 145-156. We present a simple method for improving the rendered appearance of coarse triangular meshes. We refine and modify the geometry along silhouette edges in real-time, and thus increase the geometric complexity only where needed. We address how to define the improved silhouette and a method to blend the modified and the original geometry continuously. Paper: early draft C. Dyken, The Simplified Surface Spline, Candidatus Scientiarum (M.Sc.) thesis, IfI, UiO, 2003. This thesis studies the problem of using surface splines as an approximation basis. The simplified surface spline basis, a slight simplification of the C¹-surface spline construction of Jörg Peters, is presented. The simplified surface does not guarantee a C¹ surface, but has explicit formulas, explicit basis functions and known dimension. In addition, it resides close to the C¹-surface spline. The simplified surface spline basis is employed in interpolation, least squares approximation and faired least squares approximation. In addition, the mesh notation, a notation for writing algorithms on polyhedral meshes in a concise and mathematical way, is presented. Thesis: final version. Miscellaneous debris C. Dyken, A Peek on Numerical Programming in Perl and Python, Small note comparing numerical programming in high-level languages and C, IfI/CMA, UiO, 2004. C. Dyken, Farver og interpolasjon, Essay on colour, colourspaces and interpolation in norwegian, IfI, UiO, 2000. Talks Parallel computing in video memory: A key to interactive simulations and photorealistic virtual experiences, The Industrial Gaming Track, 5th International Conference on Integrated Operations in the Petroleums Industry, Trondheim, Norway, 2009-09-29. Semi-uniform tessellations, Kongsberg SIM Hackaton, Hadeland, Norway, 2008-05-06. HistoPyramid-based stream compaction and expansion, Winter School on Parallel Computing, Geilo, Norway, 2008-01-24. HistoPyramid stream compaction and expansion, Advanced Computer Graphics and Vision seminar series, Technischen Universität Graz, Austria, 2007-10-23. Transfinite mean value interpolation, Multivariate Approximation and Interpolation with Applications (MAIA) Conference, Ålesund, Norway, 2007-08-25 Efficient gather operations using histogram pyramids, GPU as a computational resource workshop, Oslo, Norway, 2006. Web-splines for solving PDE's, CMA PDE seminar series, Oslo, Norway, 2006. Preferred directions for resolving the non-uniqueness of Delaunay triangulations, CMA internal seminar, Oslo, Norway, 2004. Improving silhouettes of coarse triangle meshes, The Sixth International Conference on Mathematical Methods for Curves and Surfaces, Tromsų, Norway, 2004. Object Orientation in Perl, Guest lecture, INF5660: Advanced Problem Solving using High-level Languages, IfI/UiO, Oslo, Norway, 2004