Sunday, February 11, 2007
More Euler
Solved 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.
Thursday, February 8, 2007
Project Euler
I came across Project Euler 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 Doo-Sabin project. I solved problems 1, 2, 6 and 9 last night and got started on 14. Some random hints/tips on the problems:
1 - trivial to solve using a list comprehension
2 - remember Fibonacci numbers get big fast
6 - sum [1 .. n] = n(n+1)/2
9 - solved using the constraint features of the Oz language
1 - trivial to solve using a list comprehension
2 - remember Fibonacci numbers get big fast
6 - sum [1 .. n] = n(n+1)/2
9 - solved using the constraint features of the Oz language
Monday, February 5, 2007
Doo-Sabin in Haskell
To 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 Farin 2000:
1 - For each face in the mesh, form new vertices as follows:
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.
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.
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:
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.
So, here is the routine to compute the new vertices:
Next up is how to compute the new faces.
1 - For each face in the mesh, form new vertices as follows:
- Form the face's centroid - average of the vertices
- Form the edge midpoints of the face
- Each new vertex is the average of a face vertex, the centroid, and the two adjacent edge midpoints.
- F-faces are constructed by joining new vertices within a face
- E-faces are constructed by joining new vertices as the edges of neighboring old faces
- V-faces are constructed by joining all new vertices around an old vertex
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.
> addVec :: RealFloat a => [a] -> [a] -> [a]
> addVec v w = [ a + b | (a, b) <- zip v w]
> scaleVec :: RealFloat a => [a] -> a -> [a]
> scaleVec v c = [a * c | a <- v]
> centroid :: RealFloat a => [[a]] -> [a]
> centroid p = scaleVec (foldl1 addVec p) (1/fromIntegral (length p))
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.
> shiftr :: [a] -> [a]
> shiftr [] = []
> shiftr (x:y) = y ++ [x]
> midPoint :: RealFloat a => [a] -> [a] -> [a]
> midPoint x y = [(a+b)/2 | (a,b) <- zip x y]
> midPoints :: RealFloat a => [[a]] -> [[a]]
> midPoints p = [midPoint a b | (a,b) <- zip p (shiftr p)]
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:
> shiftl :: [a] -> [a]
> shiftl [] = []
> shiftl x = [last x] ++ init x
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.
> shiftl (x1:x2:xs) = last:x1:init
> where last:init = shiftl (x2:xs)
> shiftl xs = xs
So, here is the routine to compute the new vertices:
> dooSabinNewVertices :: RealFloat a => [[a]] -> [[a]]
> dooSabinNewVertices n = [ centroid [c, x, y, z] | (x,(y,z)) <-
> zip n (zip m (shiftl m))]
> where
> c = centroid n
> m = midPoints n
Next up is how to compute the new faces.
Subscribe to:
Posts (Atom)