tag:blogger.com,1999:blog-80955403356236287482014-10-04T19:18:35.222-07:00Haskell Thoughts-Erichttp://www.blogger.com/profile/18034690439574339339noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-8095540335623628748.post-23368970119466135892007-02-11T21:05:00.000-08:002007-02-10T20:18:39.598-08:00More EulerSolved problems 13, 20 and 25 tonight. There are a bunch of apps on the web that will solve 3, but I'm going to tackle it without those.-Erichttp://www.blogger.com/profile/18034690439574339339noreply@blogger.com0tag:blogger.com,1999:blog-8095540335623628748.post-74885985259928088192007-02-08T07:00:00.000-08:002007-02-10T20:17:57.547-08:00Project EulerI came across <a href="http://projecteuler.net/index.php?section=about">Project Euler</a> last night and decided it would be a good diversion while I was trying to get my mind around how best to represent the data structures I need for my <a href="http://www.cs.unc.edu/%7Edm/UNC/COMP258/LECTURES/Doo-Sabin.pdf">Doo-Sabin</a> project. I solved problems 1, 2, 6 and 9 last night and got started on 14. Some random hints/tips on the problems:<br /><br />1 - trivial to solve using a list comprehension<br />2 - remember Fibonacci numbers get big fast<br />6 - sum [1 .. n] = n(n+1)/2<br />9 - solved using the constraint features of the <a href="http://www.mozart-oz.org/">Oz language</a>-Erichttp://www.blogger.com/profile/18034690439574339339noreply@blogger.com0tag:blogger.com,1999:blog-8095540335623628748.post-31797532594876779912007-02-05T20:51:00.000-08:002007-02-05T21:31:28.983-08:00Doo-Sabin in HaskellTo get more experience with Haskell, I went back to my graphics textbooks and decided to implement the Doo-Sabin algorithm for subdivision surfaces in Haskell. The Doo-Sabin algorithm refines a polygon mesh to a smooth surface. The following outline of the algorithm is from <a href="http://www.farinhansford.com/books/essentials-cagd/index.html">Farin 2000</a>:<br /><br />1 - For each face in the mesh, form new vertices as follows:<br /><ol><li>Form the face's centroid - average of the vertices</li><li>Form the edge midpoints of the face</li><li>Each new vertex is the average of a face vertex, the centroid, and the two adjacent edge midpoints.</li></ol>2 - Form new faces from the new vertices<br /><ol><li>F-faces are constructed by joining new vertices within a face<br /></li><li>E-faces are constructed by joining new vertices as the edges of neighboring old faces</li><li>V-faces are constructed by joining all new vertices around an old vertex<br /></li></ol><br />My initial thought is to represent a 3D vertex as a list. A face is then a list of vertices. I'm hijacking a couple of routines I wrote for vector math to help compute the centroid.<br /><pre><br />> addVec :: RealFloat a => [a] -> [a] -> [a]<br />> addVec v w = [ a + b | (a, b) <- zip v w]<br /><br />> scaleVec :: RealFloat a => [a] -> a -> [a]<br />> scaleVec v c = [a * c | a <- v] <br /><br />> centroid :: RealFloat a => [[a]] -> [a]<br />> centroid p = scaleVec (foldl1 addVec p) (1/fromIntegral (length p))<br /></pre><br />Time for a clever hack. I need to compute the midpoints of each edge of a face. Imagine that we have a triangular face with vertices v1, v2, v3. I need to compute the midpoint of v1v2, v2v3 and v3v1. By zipping a shifted version of my vertex list with itself, I'll have the desired vertices paired up.<br /><pre><br />> shiftr :: [a] -> [a]<br />> shiftr [] = []<br />> shiftr (x:y) = y ++ [x]<br /><br />> midPoint :: RealFloat a => [a] -> [a] -> [a]<br />> midPoint x y = [(a+b)/2 | (a,b) <- zip x y] <br /><br />> midPoints :: RealFloat a => [[a]] -> [[a]]<br />> midPoints p = [midPoint a b | (a,b) <- zip p (shiftr p)] </pre><br />Now that I have the centroid and midpoints, I just need to compute the new vertices. The trick here is to get the midpoints adjacent to a face vertex. Another shift is in order, but in the opposite direction. My initial routine was this:<br /><pre><br />> shiftl :: [a] -> [a]<br />> shiftl [] = []<br />> shiftl x = [last x] ++ init x<br /></pre><br />I don't like the fact that this routine makes two passes though the list. I posted this code to the haskell-cafe list looking for better ideas. I got this really nifty routine as a response.<br /><pre><br />> shiftl (x1:x2:xs) = last:x1:init<br />> where last:init = shiftl (x2:xs)<br />> shiftl xs = xs<br /></pre><br />So, here is the routine to compute the new vertices:<br /><pre><br />> dooSabinNewVertices :: RealFloat a => [[a]] -> [[a]]<br />> dooSabinNewVertices n = [ centroid [c, x, y, z] | (x,(y,z)) <- <br />> zip n (zip m (shiftl m))]<br />> where<br />> c = centroid n<br />> m = midPoints n<br /></pre><br />Next up is how to compute the new faces.-Erichttp://www.blogger.com/profile/18034690439574339339noreply@blogger.com0