Status Update

Project Proposal

Summary

We are going to generate and optimize a 3D triangle mesh for point clouds. If we have enough time, our reach goal would be generating the point clouds will be generated using a Xbox Kinect. The computation will be done on an NVIDIA GPU.

Background

Computer graphics revolves around the central concept of meshes. These essentially graph-like structures allow for computation to be highly parallel because usually you want to do an operation over all vertices or all edges, etc. Our goal is to generate a mesh based off a list of vertices. To do this, we must first find the nearby ‘neighborhood’ for each vertex and then connect these nearby points together in a coherent, geometrically sound way. This idea of geometrically sound is more formally known as “manifold”. A manifold mesh is essentially a mesh that doesn’t have any holes in it, no internal faces, and no overlapping edges or parts of the mesh with zero area (a popular example of this error is two pyramids connected at a single point to form an ‘hourglass’). More simply, another definition is that every edge only has a max of two faces (aka triangles) coming off of it. Once we have created a mesh, we must then try to make it optimal! This was essentially the first homework for 15-462 with three operations: 1) subdivision, 2) edge flipping, and 3) edge collapsing. What the goal of these operations are is essentially to smooth out your graph and minimize how many vertices are connected together. Subdivision breaks up a vertex into multiple vertices (finer mesh = smoother), edge flipping can result in fewer connections between certain vertices, and edge collapsing can collapse multiple triangles together (you only need two triangles to represent a plane, no more!).

So what was described above is how to connect vertices based on nearest neighbor search and then improve the quality of your mesh based on a few atomic operations. This works if our point cloud is well defined. If we get to our reach goal of using the connect though, it is possible we may deal with bad point clouds! This idea of a ‘noisy’ mesh could be combatted by A) threshold how far away the nearest neighbor can be to detect ‘outlier’ points and B) use the aforementioned algorithm to smooth out bumpy surfaces by downsampling and then upsampling. That’s the rough idea of our approach! It is nicely segmented into three steps: 1) creation of mesh, 2) improvement of mesh, and 3) using kinect to generate a point cloud. How optimal #1 is determines how long #2 takes. Doing #1 in parallel requires a lot of communication between processes (imagine creating separate meshes and ‘gluing’ them together at their edges. Algorithms like nearest neighbor and noise reduction are highly parallelizable whereas connecting connecting vertices via edges is highly serial (although we could create multiple meshes and ‘glue’ them together at the end as previously stated.

The Challenge

There are a couple issues for this project. The first difficulty is with regards to memory. GPUs do not have a large amount of space, thus most of the data needs to be in DRAM (especially for large point clouds). The second and more difficult problem is generating partial meshes on different cores and combining them after computation. These two challenges go hand in hand, particularly if the initial point cloud is very large and we cannot completely compute all the sections of the point cloud in one go. We hope to learn how to deal with the memory constraint and improve performance (via load balancing) while keeping correctness.

Resources

Code: C++, Cuda, PCL libraries (optional: for point cloud generation and visualization)

Hardware: Microsoft Kinect (for capturing point clouds), Nvidia GPU (might be able to use the GHC servers)

We are planning on doing a triangle mesh. We will be doing more research on this, but Delaunay Triangulation is an option we are thinking about based on an initial search.

^ We will ideally find a paper for a rough outline of how to make sure we build a valid mesh.

^^ We would need access to a kinect as we do not have one ourselves.

Goals and Deliverables

The nice thing about our project is that it is implemented in steps. Step 1 is to find a way to display points and triangles on our screen (seeing as these are all solid figures, a simple rasterizer could either be found online or written based on old 15462 code). Step 2 is to generate the mesh based on a list of vertices (we expect this step to take the most time). Step 3 is improve the mesh using the operations described in background (Jordan has implemented these before and says they are highly parallelizable so this step should be easy). Step 4 is using a point cloud based off kinect. Before this step, we will just download obj meshes off the internet and delete their edges so that we are working with ideal meshes. Working with a point cloud shouldn’t be too much harder, it just might require correcting for error. Thus our milestones are these:

Basically, step 1 and 4 are the easy GUI steps, steps 2 and 3 are where the majority of the project will be, and steps 5 and 6 are cool things to visualize our project with if we have time.

Platform Choice

PCL is a very good library for point clouds and is already implemented in C++. We are very familiar with C++ and Cuda which will make our development speed faster. Microsoft Kinect is a great resource for capturing point clouds at medium distances. If we want to capture close range point clouds, we may want to choose a different depth camera (such as DepthSense from SoftKinectic).

Schedule