1SMARTPAPER:An Interactive and User Friendly Sketching SystemPresented by Brian WilliamsonWritten by: Amit Shesh and Baoquan ChenPresentation Overview• Introduction to the problem• 3D rendering techniques using sketch based interfaces• SMARTPAPER’s features• Processing Pipeline– 2D processing– 3D Geometry Reconstruction• Feedback/Cutting/Joining/Rendering• Conclusion2Introduction• It is natural to sketch out a 3D object conceptually• Current methods involve taking a conceptual sketch and using a complex system (such as CAD) to create it• A better design would be to allow the sketched interface to immediately translate to a 3D objectFree Form recognition (TEDDY)• Draw any design• Used fewer gestures• May want simple ways for primitive objects• Algorithm may create “cartoon looking” models3Gesture Rendering (SKETCH)• Uses several gestures• Simple to create primitives• May be unintuitive (depends on gesture set)2D Graph Formation• Proposed by Lipson (1996)• Scanned in 2D sketches• Built 2D graph information (vertices, edges)• Render from graph4Introducing SMARTPAPER• A combination of the other techniques• Allow free form drawing• Allow gesture manipulation• Render from 2D graphsObject Creation• Can draw an object• Use an arrow to extrude it out• Object can be primitive or freeform• Can perform incremental construction5Attaching Objects• Can attach an object with a line• The line determines which face of the object attaches• Example shows ground planeObject Cutting• Cut an object by drawing into it• Can draw an extrusion line to completely remove6Putting it all together (Lamp example)The BaseThe StandThe ShadeThe LampHow is this done?7Clean Sketch and Recognize GesturesForm 2D GraphDetermine Faces3D ReconstructionDetermine Cutting Planes and cut solidUser Feedback, Cluster Threshold, and face determination method selectionProcessing PipelineExample Stages• Input Sketch– Rough Drawing• Cleaned Sketch– Remove Overtracing– Clean Imperfections• Recognized Faces– Create 2D graph• Recognized Object– Built from 2D graph8Pre-Processing: Over Tracing• Remove Over Tracing– A pair of strokes A,B are over tracing if:– They have nearly equal slopes– One End Point of A lies in the X and Y ranges of the endpoints of B• Once found, a connection is made in two passes, A’s starting point to B’s ending pointOver tracing ExamplePre-Processing: Gesture Recognition• Arrow was recognized as proof of concept– Has to be drawn in two strokes– Both recognizer and cutting modules query if this gesture was drawn– Either recognizer or cutting module is called depending on the operation92D Graph Generation• Graph is generated with a connectivity matrix, each vertex contains (x,y) coordinates• Imagine taking the endpoints from each line to create vertices• If performing extrusion, a copy of one graph is made along the direction of the extrusion arrow and edges are connected• Then use “clustering” to determine proximity and combine graphs• We assume all sketches are closed objects– All vertices must have at least a degree of 3– Remove any vertex that does not meet this ruleClustering Method• As edges are added to the graph, all end points with a distance of some threshold sigma from an existing vertex are grouped with it.• Sigma can be changed in the feedback systemSigma103D Reconstruction: Face Determination• All Faces are Cycles• Not all cycles are faces though• Using the closed object assumption– All edges of graph G are part of exactly two faces– The shortest path of any two vertices V1, V2 is the same length as the path in the face F– Proof by contradiction (Available in backup slides)• Two algorithms are used to determine faces– Edge Coherence Algorithm– Modified Dijkstra AlgorithmEdge Coherence Algorithm• 3D objects are not drawn randomly• Chances are, faces are drawn together• First Pass: O(e)– Can check for cycles in sequential edges for the possibility of a face– If two edges do not connect, use a lookahead (1 in the paper) to find a connection– With connected edges, attempt to close the temporary face• Second Pass: O(e1 * n^2) – For all unclosed faces and edges not part of two faces– Find shortest path of the two vertices• Works most of the time, but erasing strokes and redrawing strokes will not determine faces11Edge Coherence Pseudo CodeModified Dijkstra Algorithm• Take an edge E and find the shortest path from one end point to the other• Modified in a way that all edges already determined for a face are removed, and cannot be used in the algorithm12Dijkstra Pseudo Code3D Reconstruction• “Inflate” the object by assigning Z values using geometric properties– Use planarity of faces, parallelism, etc• Make use of compliance function• F(Z) = W * SUM(A)• Where A is the vector of all factors, W is a weighting function and Z is the z value for all vertices• This is an N-dimensional optimization problem– Used Brent’s Minimization technique to reduce to several 1-dimensional optimization problems– Go cyclically, Vertex by Vertex, attempting to approach equilibrium• User can provide hints (dotted lines) to help with reconstruction13More on 3D Reconstruction• Using hints, create three Z layers– One layer consists of vertices to which only hidden edges are incident– Second layer is of vertices to which only visible edges are incident– Third layer is all other vertices• These layers give each vertex an initial Z value• The 3D object is finally represented as a new graph, similar to boundary representation (B-Rep)– Boundary Representation is a representation of faces, edges, and vertices. It is currently used in CAD systems.• Use this graph to reproject when using different viewpointsReconstruction Example14Offering User Feedback• Clustering may be incorrect• Leads to incorrect FacesMore User Feedback• Can switch face detection algorithm15Cutting• Performed by drawing on a 3D object• Convert strokes to 2D graph• Cast ray from eye position through both end vertices of each edge• Arrow uses ray casting to determine direction• Cut from the object once the plane has been generated• Cutting algorithm discussed in “Boolean Operations of 2-Manifolds through vertex neighborhood classification”– Uses Boolean operations to cut from 3D B-Rep graph representationJoining• Uses the