1 ---------------------------------------------------------------------------- outline - introduction - what concepts are needed - 2D version - curves - 3D version - how to extend to 3D - show some pictures - give my conclusion 2 ---------------------------------------------------------------------------- introduction - Amenta, Bern 1998 - project based on Surface Reconstruction by Voronoi Filtering - paper by Amenta & Bern in 1998 - why do we want to reconstruct surfaces? - useful for laser range data, medical images, cartography, and stuff - why not use an existing algorithm? - This differs from previous algorithms in that surfaces are not required to be uniformly sampled (i.e. density vary with level of detail) - couldn't really test it out in my project 3 ---------------------------------------------------------------------------- concepts - convex hulls - don't really need to define - voronoi diagram [voronoi.jpg] - divide into regions where all pts are closest to a vertex - intersection are the voronoi vertices - delaunay triangulation [delaunay.jpg] - graph dual of VD 4 ---------------------------------------------------------------------------- curve reconstruction - given sample points S 1. compute voronoi vertices V of S 2. compute delaunay triangulation of S & V 3. select edges with end points in S - [curve1.jpg] point set & voronoi diagram - [curve2.jpg] delaunay triangulation of all pts, with the selected edges highlighted - overall concepts are pretty simple - easier to understand in 2D - similar in 3D, except - you are selecting triangles, not edges - some modifications needed 5 ---------------------------------------------------------------------------- extension to surfaces - problem: - voronoi vertices can lie very close to the sample surface. - this punches holes in the reconstructed surface. - [holepunch.jpg] red is the voronoi cell for the blue vertex. one of the voronoi vertices is very close to the surface. this creates a hole when the delaunay triangulation use the voronoi vertex instead of a sample pt. - solution: use poles. select the 2 farthest voronoi vertices, one on each side of the surface, a +ve & a -ve pole. - also need to refine the surface. 6 ---------------------------------------------------------------------------- a happy picture - [octahedron.jpg] - uniform sampling - it works. 7 ---------------------------------------------------------------------------- a happy-looking picture - [hypersheet.jpg] - sampling is still fairly uniform - it looks like it works. but does it? 8 ---------------------------------------------------------------------------- refinement - filtering by normal is removing triangles based on the direction of their face normal. Idea is that you will get rid of triangles whose face normal differs too much from the surface normal. the pictures are from the hypersheet before. - [hypersheet-prefilter.jpg] - before any filtering. gray is what will be filtered out. - this is part of the hypersheet - [hypersheet-filter100.jpg] - after filtering, with a parameter angle of 100. - surface looks like a 2 manifold. - you can see there are pockets in the surface where the lower gray triangles were removed. - but some of the removed triangles also cause holes in the surface. - [hypersheet-filter101.jpg] - filtering with an angle of 101. - now there are no holes, but one of the pockets is back. (2nd "row", 2nd gray triangle from bottom) - have to play with the parameter, unless you know the sampling density. 9 ---------------------------------------------------------------------------- - want consistent definition of outside and inside. so call side visible from p+ outside, and p- inside (remember poles are supposed to be one on each side of the surface) Flip triangles and poles in a breadth first search manner. this is what you get. - [hypersheet-1side.jpg] - previous hypersheet looks good because it is lighted on 2 sides. When it is lighted on one side, can see that the orientation doesn't look consistent. - [hypersheet-flipped.jpg] - one reason is that the poles we pick aren't really one on each side of the surface. But how can you ensure that the poles you pick will be one on each side? - I don't think you can, 'cause you don't know what the surface is like when you pick the poles. - yellow triangles are flipped - lines are lines from each vertex to it's poles - note that the triangles with the wrong orientation has one or more of it edge vertex with poles that lie on one side only. - trim off pockets and slivers - second part of this refinement. didn't do this part, so not going to talk about it. 10 ---------------------------------------------------------------------------- some unhappy pictures [golfclub.jpg] - probably shouldn't have to use subdivision data - level of detail. part of golf club is flat, but the flat part is really thin, so you need lots of sample points. [unhappymickey.jpg] - suppose to be mickey mouse. random sample points made by steve. - problems with the library. Don't use Qhull. It's not computing the delaunay triangulation correctly. Also tried to generate some data, but Qhull crashes or computes a convex hull that is wrong. Can't handle co-planar points. [mickey.jpg] - better looking mickey. Steve twisted 1 ear slightly so points are not so co-planar. Still full of holes. this is lighted on both sides. Extra triangles mostly between the ears. hard to tell there are pockets and stuff from the pictures. [spock.jpg] - Orientation problem - here backfacing polygons are wire-framed. hole problem as well. 11 ---------------------------------------------------------------------------- conclusion - couldn't really test the density thing, main appeal of the algorithm, because the convex hull library I used generates wrong convex hulls, vd, delaunay and core dumps when there are too many co-planar pts. - so if you do this, don't use qhull. - there are some problems with orientation, extra triangles or pockets, and lots of holes with the data I use - I'm sure the algorithm works on perfect data, I don't know how easy it is to get that kind of data.