-
Notifications
You must be signed in to change notification settings - Fork 15
/
2017.html
268 lines (229 loc) · 20.8 KB
/
2017.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
---
permalink: /gsoc/2017.html
layout: page
title: CGAL - Project Ideas for the Google Summer of Code 2017
header: CGAL - Project Ideas for the Google Summer of Code 2017
group: navigation
---
{% include JB/setup %}
<h2>Accepted Projects</h2>
<p>
The CGAL Project was a mentoring organization of the <a href="https://summerofcode.withgoogle.com/">Google Summer of Code</a> in 2017.
Successful projects can be found <a href="https://summerofcode.withgoogle.com/archive/2017/organizations/6565611412914176">here</a>.
</p>
<h2>Project Ideas</h2>
<p>
On this page we presented some project ideas for the Google Summer of Code 2017.
</p>
<p>
Previous project ideas of the CGAL project for the Google Summer of Code can be found on the following pages:
<a href="2010.html">2010</a>, <a href="2011.html">2011</a>,
<a href="2012.html">2012</a>, <a href="2013.html">2013</a>,
<a href="2014.html">2014</a>, <a href="2015.html">2015</a>,
<a href="2016.html">2016</a>.</p>
</p>
<h3>Summary:</h3>
<p>
First section to read: <a href="#information">Information Candidates Should Supply</a>
</p>
<ol>
<li> <a href="#p1">Adding a Parallel Version of the Edge Simplification Algorithm</a>
<li> <a href="#p2">Reworking Intersection Functions</a>
<li> <a href="#p3">Enhancing the 2D Arrangement Demo (1)</a>
<li> <a href="#p4">Enhancing the 2D Arrangement Demo (2)</a>
<li> <a href="#p5">Create a Bridge Between the Available Github "webhooks", and the Usual Git Hook Scripts</a>
<li> <a href="#p6">Finalizing a Package for 2D Triangulations on the Sphere</a>
<li> <a href="#p7">Improving Poisson Surface Reconstruction</a>
<li> <a href="#p8">Improving Normal Orientation</a>
<li> <a href="#p9">Hexahedral Mesh Extraction</a>
<li> <a href="#p10">Mesh Smoothing and Shape Smoothing</a>
<li> <a href="#p11">Integrating PinMesh in CGAL</a>
<li> <a href="#p12">Interfacing <code>NearptD</code> with Point Set Processing algorithms of CGAL</a>
</ol>
<!------------------------------------------------------------------------------------------------------------------------------------------------------------>
<hr>
<h3 id="p1">Adding a Parallel Version of the Edge Simplification Algorithm</h3>
<p><b>Mentor(s):</b> Sebastien Loriot (GeometryFactory) and Clement Jamin (INRIA)
</p><p><b>Project description:</b><br />
CGAL has a triangulated surface mesh edge simplification <a rel="nofollow" class="external text" href="http://doc.cgal.org/latest/Surface_mesh_simplification/index.html">package</a>
based on the paper <i>Peter Lindstrom and Greg Turk. Fast and memory efficient polygonal simplification. In IEEE Visualization, pages 279-286, 1998.</i>
The goal of this project is to be able to run the edge simplification algorithm in parallel.
There are several ways to achieve it:
<ul>
<li> modify the current algorithm so that several thread can work on the simplification.
<li> implement a method to decompose the meshes into submeshes and run the algorithm sequentially on each part + special care for the stitches.
<li> implement another method that is better and designed for parallel computing.
</ul>
The choice of the approach is left to the candidate.
</p><p><b>Required Skills:</b> C++, Intel TBB
</p><p><b>Contact:</b> [email protected]
</p>
<!------------------------------------------------------------------------------------------------------------------------------------------------------------>
<hr>
<h3 id="p2">Reworking Intersection Functions</h3>
<p><b>Mentor(s):</b> Sebastien Loriot
</p><p><b>Project description:</b><br />
The goal of this project is to rewrite all the intersection predicates (<code>do_intersect_2/3</code>) to provide more information, but at the same time staying backward compatible. For example, say you want to know whether two segments intersect but also where lies the intersection, in the interior or at an endpoint of each segment. If the student is fast enough, an extension of the project is to rewrite intersection computation functions to take into account the result of the do-intersect predicate to speed up the computation.
</p><p><b>Required Skills:</b> C++, generic programming, basic geometry
</p><p><b>Contact:</b> [email protected]
</p>
<!------------------------------------------------------------------------------------------------------------------------------------------------------------>
<hr>
<h3 id="p3">Enhancing the 2D Arrangement Demo (1)</h3>
<p><b>Mentor(s)</b>: Efi Fogel (Tel Aviv University)
</p><p><b>Project description:</b><br />
Currently the demo supports (linear) segments, polylines, conic arcs, linear curves, and circular arcs. The goal of this project is to enhance the 2D arrangement demo to support additional types of curves, namely, Bezier curves and algebraic curves.
</p><p>This is a perfect project for GSoC. A developer that commits to pursue the goals of this project will learn to use the 2D arrangement package, other components of CGAL, and other libraries, such as QT. The purpose of the CGAL demos is to demonstrate the potential of the various components of CGAL using visual effects. The excitement and satisfaction, a developer of an application experience, are always enhances when visual effects are exploited. Demo programs of CGAL show the capabilities of the library and help the community evaluating it. A potential user can quickly determine whether a specific component of CGAL can be used to solve a problem she or he may have and how to go about it.
</p><p><b>Required Skills:</b> C++, generic programming, basic geometry
</p><p><b>Contact:</b> [email protected]
</p>
<!------------------------------------------------------------------------------------------------------------------------------------------------------------>
<hr>
<h3 id="p4">Enhancing the 2D Arrangement Demo (2)</h3>
<p><b>Mentor(s)</b>: Efi Fogel (Tel Aviv University)
</p><p><b>Project description:</b><br />
Currently the demo supports only arrangements in the plane. The goal of this project is to enhance the 2D arrangement demo to support 2D arrangements not only embedded in the plane, but also embedded in certain surfaces in space, e.g., arrangements of arcs of great circles embedded in the sphere. This is an upcoming feature of the "2D Arrangements" package.
</p><p>Like the project above, this is also a perfect project for GSoC. A developer that commits to pursue the goals of this project will learn to use a significant upcoming feature of the "2D Arrangements" package that supports 2D arrangements on 3D surfaces. Similar to the project above, the developer will learn to use other components of CGAL, and other libraries, such as QT. The purpose of the CGAL demos is to demonstrate the potential of the various components of CGAL using visual effects---an enjoyable side effect of developing such applications especially when 3D graphics is involved. Demo programs of CGAL show the capabilities of the library and help the community evaluating it. A potential user can quickly determine whether a specific component of CGAL can be used to solve a problem she or he may have and perhaps how to go about it.
</p><p><b>Required Skills:</b> C++, generic programming, basic geometry, basic 3D graphics
</p><p><b>Contact:</b> [email protected]
</p>
<!------------------------------------------------------------------------------------------------------------------------------------------------------------>
<hr>
<h3 id="p5">Create a Bridge Between the Available Github "webhooks", and the Usual Git Hook Scripts</h3>
<p><b>Mentor(s):</b> Laurent Rineau
</p><p><b>Project description:</b><br />
The CGAL project has moved from a dedicated Git repository to the Github service. One issue is that Github no-longer support the server Git hooks, but only its own instance named "webhook". The student will implement a bridge between Github webhooks and usual Git hook scripts, so that one can for example use <a rel="nofollow" class="external text" href="https://github.com/mhagger/git-multimail">git-multimail</a> with Github.
</p><p><b>Required Skills:</b> shell programming, web services
</p><p><b>Contact:</b>: [email protected]
</p>
<!------------------------------------------------------------------------------------------------------------------------------------------------------------>
<hr>
<h3 id="p6">Finalizing a Package for 2D Triangulations on the Sphere</h3>
<p><b>Mentor(s):</b> Sebastien Loriot (GeometryFactory) and Monique Teillaud (INRIA)
</p><p><b>Project description:</b><br />
The sphere can model atoms (biology) as well as the earth (geography) and the celestial vault (astrophysics), which shows a strong need for computations on the sphere. A method was proposed, a few years ago, to compute triangulations of points on or close to a sphere [1], and a prototype software has been written. The prototype is very efficient, but it duplicates some parts of the CGAL 2D triangulation classes. The project will consist in proposing a new design for those classes in order to avoid duplications, and implementing it.
</p><p><b>Required Skills:</b> C++, design patterns
</p><p><b>Contact:</b> [email protected], [email protected]
</p><p><b>Reference</b><br />
[1] Manuel Caroli, Pedro M. M. de Castro, Sebastien Loriot, Olivier Rouiller, Monique Teillaud, and Camille Wormser. Robust and Efficient Delaunay triangulations of points on or close to a sphere. In 9th International Symposium on Experimental Algorithms, volume 6049 of Lecture Notes in Computer Science, pages 462-473, 2010. Preliminary version available at <a rel="nofollow" class="external free" href="https://hal.inria.fr/inria-00405478/">https://hal.inria.fr/inria-00405478/</a>
</p>
<!------------------------------------------------------------------------------------------------------------------------------------------------------------>
<hr>
<h3 id="p7">Improving Poisson Surface Reconstruction</h3>
<p><b>Mentor(s):</b> Pierre Alliez (Inria), Gael Guennebaud (Inria) and Simon Giraudot (GeometryFactory)
</p><p><b>Project description:</b><br />
The current implementation from CGAL: <a rel="nofollow" class="external free" href="http://doc.cgal.org/latest/Poisson_surface_reconstruction_3">http://doc.cgal.org/latest/Poisson_surface_reconstruction_3</a> can be improved along two axes: scalability and smoothness of the reconstructed surfaces.
The scalability is hampered by the fact that the Poisson solver requires a space discretization: a Delaunay triangulation generated via Delaunay refinement, and a matrix assembly. A first direction is to reduce the complexity of the triangulation. A second direction is a hash data structure inspired by [1]. A third direction is to investigate a matrix-free approach where the implicit function is computed in closed form using a far field approximation.
On smoothness of the output surfaces, the current issue is that the current implicit surface is piecewise linear as computed on a piecewise linear 3D function. We will investigate local smooth interpolation approaches that yield smooth surfaces at all scales. Another issue arises on surfaces with boundaries. We will devise an approach that generate smooth curves as boundaries.
</p><p><b>Required Skills:</b> C++, geometric data structures, applied maths.
</p><p><b>References</b><br />
[1] <a rel="nofollow" class="external free" href="http://mesh.brown.edu/ssd/software.html">http://mesh.brown.edu/ssd/software.html</a>
</p>
<!------------------------------------------------------------------------------------------------------------------------------------------------------------>
<hr>
<h3 id="p8">Improving Normal Orientation</h3>
<p><b>Mentor(s):</b> Pierre Alliez (Inria), Gael Guennebaud (Inria) and Simon Giraudot (GeometryFactory)
</p><p><b>Project description:</b><br />
The current CGAL approach for normal orientation <a rel="nofollow" class="external free" href="http://doc.cgal.org/latest/Point_set_processing_3">http://doc.cgal.org/latest/Point_set_processing_3</a> proceeds by propagation along a minimum spanning tree. While this approach is satisfactory for noise-free connected point sets, it fails on disconnected point sets with high noise. The first objective is to evaluate two more recent approaches on a wide range of point sets [1,2]. The second objective is to implement the best approach as a CGAL algorithm. The third objective is to investigate the use of an existing approach [3] based on the construction of an signed implicit function from unoriented points, in order to deduce the normal orientation.
</p><p><b>Required Skills:</b> C++, geometric data structures, applied maths.
</p><p><b>References</b><br />
[1] Consolidation of Unorganized Point Clouds for Surface Reconstruction. H. Huang, D. Li, H. Zhang, U. Ascher, D. Cohen-Or. ACM Transactions on Graphics (Proceedings of SIGGRAPH ASIA) 2009.
</p><p>[2] Towards Globally Optimal Normal Orientations for Large Point Clouds. N. Schertler, B. Savchynskyy, S. Gumhold, In Computer Graphics Forum, 2016.
</p><p>[3] Voronoi-based Variational Reconstruction of Unoriented Point Sets. P. Alliez, D. Cohen-Steiner, Y. Tong, and M. Desbrun. In Proc. 4th Annu. Sympos. Geometry Processing, pages 39-48, 2007.
</p>
<!------------------------------------------------------------------------------------------------------------------------------------------------------------>
<hr>
<h3 id="p9">Hexahedral Mesh Extraction</h3>
<p><b>Mentor(s):</b> Guillaume Damiand (CNRS/LIRIS)
</p><p><b>Project description:</b><br />
Implement the method given in the paper "HexEx: Robust Hexahedral Mesh Extraction", Max Lyon, David Bommes, Leif Kobbelt, SIGGRAPH 2016. In this paper, authors defined a method to extract an hexahedral mesh from 2D surfacic mesh. This methods uses 3D generalized map which are now available in CGAL. Authors paper and code are available here [1]. The goal of this project is to implement the method in CGAL based on the 3D generalized map package.
</p><p><b>Required Skills:</b> C++, geometric data structures.
</p><p><b>Contact:</b> [email protected]
</p><p><b>References</b><br />
</p>
<ul>
<li> [1] <a rel="nofollow" class="external free" href="https://www.meshing.rwth-aachen.de/publication/03260/">https://www.meshing.rwth-aachen.de/publication/03260/</a>
</li>
</ul>
<!------------------------------------------------------------------------------------------------------------------------------------------------------------>
<hr>
<h3 id="p10">Mesh Smoothing and Shape Smoothing</h3>
<p><b>Mentor(s):</b> Jane Tournois (GeometryFactory), Pierre Alliez (Inria)
</p><p><b>Project description:</b><br />
Mesh Smoothing and Shape Smoothing (or Geometric Smoothing) are often needed to improve the quality of a surface mesh. The choice of quality criterion (angles, edge lengths, smoothness, noise,...) leads the choice of the optimizer. Many algorithms that provide solutions for geometric smoothing
and mesh smoothing are available in the literature. The goal of this project is to implement and publish some of the State-of-the-Art algorithms in the
<a rel="nofollow" class="external text" href="http://doc.cgal.org/latest/Polygon_mesh_processing/index.html">CGAL Polygon Mesh Processing package</a>.
</p>
<ul>
<li> Geometric Smoothing includes the <i>Mean Curvature Flow</i> [1] and its volume preserving and feature preserving variants.
</li>
<li> Mesh Smoothing includes the <i>High Quality Compatible Triangulations</i> [2] and methods that are angle-based or area-based.
</li>
</ul>
<p>This work can be extended by providing a generic framework to optimize a user-defined criterion such as normals, colors,...
</p><p><b>Required Skills:</b> C++, geometric data structures, generic programming.
</p><p><b>Contact:</b> [email protected]
</p><p><b>References</b><br />
</p>
<ul>
<li> [1] <a rel="nofollow" class="external text" href="https://www.researchgate.net/profile/Mathieu_Desbrun/publication/221326461_Processing_Irregular_Meshes/links/0deec52bb6fcc1f898000000.pdf">Implicit fairing of irregular meshes using diffusion and curvature flow</a> Desbrun, Meyer, Schroder, and Barr (1999).
</li>
<li> [2] <a rel="nofollow" class="external text" href="http://www.imr.sandia.gov/papers/imr11/surazhsky.pdf">High quality compatible triangulations</a> Surazhsky and Gotsman (2004)
</li>
</ul>
<!------------------------------------------------------------------------------------------------------------------------------------------------------------>
<hr>
<h3 id="p11">Integrating PinMesh in CGAL</h3>
<p><b>Mentor(s):</b> Salles Viana Gomes de Magalhaes (Universidade Federal de Viçosa), Andrade Marcus (Universidade Federal de Viçosa), W. Randolph Franklin(Rensselaer Polytechnic Institute), Andreas Fabri(GeometryFactory)</p>
<p> PinMesh is a very fast algorithm with implementation to preprocess a
polyhedral mesh, also known as a multi-material mesh, in order to
perform 3D point location queries. PinMesh combines several innovative
components to efficiently handle the largest available meshes. CGAL also have a <a href="http://doc.cgal.org/latest/Polygon_mesh_processing/classCGAL_1_1Side__of__triangle__mesh.html
">class</a> for answering such queries, but it is not optimized for large meshes. The goal of this project is to integrate the code of PinMesh into CGAL so that it can be used
as an alternative implementation of <code>Side_of_triangle_mesh</code>.
</p><p><b>Required Skills:</b> C++, generic programming.
</p><p><b>Contact:</b> [email protected]
<!------------------------------------------------------------------------------------------------------------------------------------------------------------>
<hr>
<h3 id="p12">Interfacing <em>NearptD</em> with Point Set Processing algorithms of CGAL</h3>
<p><b>Mentor(s):</b> W. Randolph Franklin(Rensselaer Polytechnic Institute), Andreas Fabri(GeometryFactory)</p>
<p>
<a href="https://github.com/Lucky1313/NearptD"><em>NearptD</em></a> is a nearest neighbor search
software that is using a uniform grid to enable the use of the GPU for doing faster queries.
CGAL provides a k-nearest neighbor data structure running only on the CPU. The goal of this project is
to replace in <a href="http://doc.cgal.org/latest/Point_set_processing_3">point set processing</a> algorithm of CGAL the nearest neighbor implementation by the one of NearptD.
Benchmark will them be done to see if the replacement could be useful in practice. If so, a proper integration
should be done.
</p>
</p><p><b>Required Skills:</b> C++, generic programming, GPU.
</p><p><b>Contact:</b> [email protected]
<!------------------------------------------------------------------------------------------------------------------------------------------------------------>
<hr>
<h3 id="information">Information Candidates Should Supply</h3>
<p>The application process has several steps. Before contacting anybody verify that you are eligible, that is
that you are enrolled as student, don't get a tuition fee, etc. The next step is to contact the mentor
of the project you are interested in. You have to convince him that you are the right person to get the job
done. The next step is to work out more details and to contact the mentoring organization by providing
the following information by email to <a href="mailto:[email protected]">[email protected]</a></p>
<h4>Project</h4>
<ol>
<li> Select a project in the list and provide your personal and detailed description. If you wish to work on another idea of your own, we are pretty open as long as this serves the goal of consolidating CGAL as a whole.
<li> Provide a proposal of a technical solution with your envisioned methodology. The more detailed the better.
<li> Explain how the solution will be available to the user, in which form. Do not forget the documentation, unitary tests and cross-platform aspects.
<li> Provide a realistic schedule with objectives (one every two weeks for example) and deadlines. Focus on mid-term objectives as well as on the final evaluation.
<li> Provide a formal commitment that you will be involved full time on the GSoC. This is absolutely mandatory.
</ol>
<h4>Personal data</h4>
<ol>
<li> First name, last name, affiliation and geographical location.
<li> A brief list of the main studies and programming courses attended, with ranking.
<li> List of the most important software projects contributed and success.
<li> Which are your best skills in terms of programming and scientific computing?
<li> In general what is your taste in terms of programming? language, methodology, team work, etc.
<li> Is there anything that prevents you from working full time on the project during the program period?
<li> How do you see your involvement after the program ends? Do you see yourself pushing the project further, or do you see yourself contributing to other CGAL projects?
<li> Are you more interested in the theory/scientific aspect of CGAL, or do you feel more like a hacker?
<li> What are your long-term wishes in terms of job?
</ol>