# Oleksandr Kaleniuk - Geometry for Programmers (Highlights)  ## Metadata **Review**:: [readwise.io](https://readwise.io/bookreview/39682119) **Source**:: #from/readwise #from/zotero **Zettel**:: #zettel/fleeting **Status**:: #x **Authors**:: [[Oleksandr Kaleniuk]] **Full Title**:: Geometry for Programmers **Category**:: #books #readwise/books **Category Icon**:: 📚 **Highlighted**:: [[2024-04-16]] **Created**:: [[2024-04-19]] ## Highlights - But another convention comes from matrices: the i-j row-column convention. The i is the row index, and j is the column index. Note that this notation is inverse of x-y. The j index corresponds to the horizontal axis, which is usually x, and the i index is vertical, which is usually y. ([Page 20](zotero://open-pdf/library/items/ZQ5NT2VZ?page=43&annotation=DSQDHLKU)) ^707486250 - A, B, C, D, and infinitely more points from inside the triangle are the triangle’s points. Any point that belongs to a triangle, including the triangle’s interior surface, is a triangle’s point. ([Page 25](zotero://open-pdf/library/items/ZQ5NT2VZ?page=48&annotation=5WRV4KVJ)) ^707486251 - While we’re being pedantic, do you know the difference between a point on a triangle and a point in a triangle? ([Page 25](zotero://open-pdf/library/items/ZQ5NT2VZ?page=48&annotation=9Z7AQYSG)) ^707486252 - Degenerate triangles can be either of two types: needles and caps (figure 2.10). ([Page 26](zotero://open-pdf/library/items/ZQ5NT2VZ?page=49&annotation=272SN36Y)) ^707486253 - Normally, when you model some shape with a bunch of triangles, your model implies that a triangle may have up to three neighbors. If you organize your geometric model this way, the triangles that represent the model are called a triangle meshmore specifically, a manifold triangle mesh. ([Page 26](zotero://open-pdf/library/items/ZQ5NT2VZ?page=49&annotation=RFU9H8I6)) ^707486254 - Degenerate triangles make mesh processing needlessly difficult. When you’re using a compound mesh operation, it’s usually advisable to clean any degenerate triangles out of your model before doing anything else. ([Page 27](zotero://open-pdf/library/items/ZQ5NT2VZ?page=50&annotation=3G2A63JN)) ^707486255 - One way, perhaps the most popular, is to measure the proportion of its inscribed circle radius to its circumscribed circle radius. This proportion is also known as the Rin/Rout metric. ([Page 27](zotero://open-pdf/library/items/ZQ5NT2VZ?page=50&annotation=66KWRIZX)) ^707486256  - A line in 3D isn’t set by a single equation, but by a pair of equations. ([Page 31](zotero://open-pdf/library/items/ZQ5NT2VZ?page=54&annotation=K9TWL2ZV)) ^707486257 - This way of denoting lines is called a parametric form. ([Page 32](zotero://open-pdf/library/items/ZQ5NT2VZ?page=55&annotation=XN8HUE3N)) ^707486258 ↩︎ $ \begin{align*} x &= f_x(t) \\ y &= f_y(t) \end{align*} $ - A function is a special case of a relation. It’s also a rule, and it links one or many input values with the output values, but it’s not allowed to link many output values to a single input. ([Page 35](zotero://open-pdf/library/items/ZQ5NT2VZ?page=58&annotation=G7TIUD22)) ^707486259 - Speaking in programming terms, the codomain is the output type of the function, whereas the range is all the possible values the function can produce. ([Page 36](zotero://open-pdf/library/items/ZQ5NT2VZ?page=59&annotation=LJGITR5W)) ^707486260 - The domain, confusingly, isn’t the type, as in a codomain, but all the possible values, as in a range. ([Page 36](zotero://open-pdf/library/items/ZQ5NT2VZ?page=59&annotation=BGPEVT26)) ^707486261 - The most important function, discussed in two chapters later in the book, is called a geometric transformation. It’s a function that turns a point into another point, normally, in the same space. ([Page 38](zotero://open-pdf/library/items/ZQ5NT2VZ?page=61&annotation=DXCX32YQ)) ^707486262 - A similar kind of function is called a vector field. It defines an M-dimensional vector for every point of N-dimensional space. Its domain is , and its codomain is . M and N can be the same, of course, but this isn’t always the case. ([Page 38](zotero://open-pdf/library/items/ZQ5NT2VZ?page=61&annotation=TBC32HB8)) ^707486263 A field relates each point to a vector. - A vector field that stands behind a geometric transformation specifically is called a deformation field (figure 2.25). It’s a rule that describes how you should translate or move points of some space, depending on where these points are. ([Page 39](zotero://open-pdf/library/items/ZQ5NT2VZ?page=62&annotation=KBESHU5F)) ^707486264 - Another special case of a function is a scalar field, which is like a vector field but assigns a scalar, also known as a real number, for every point. Its domain is , and its codomain is . ([Page 40](zotero://open-pdf/library/items/ZQ5NT2VZ?page=63&annotation=LM2LVFBB)) ^707486265 - One example of these fields is a signed distance function, or SDF for short (figure 2.26). An SDF is a distance to a curve or a surface in 3D defined for all the points in space. The distance function is called signed because we set it positive for points outside the body and negative for the points inside the body. ([Page 40](zotero://open-pdf/library/items/ZQ5NT2VZ?page=63&annotation=GGKYLRBL)) ^707486266 - Two algebraic systems are isomorphic if, and only if, they operate on sets that have one-to-one correspondence that allows all the algebraic properties from one set to work on another. ([Page 42](zotero://open-pdf/library/items/ZQ5NT2VZ?page=65&annotation=GL649SFH)) ^707486267 - As a general rule, if N different N-hyperplanes intersect in N-dimensional space, they all intersect at exactly the same point. ([Page 51](zotero://open-pdf/library/items/ZQ5NT2VZ?page=74&annotation=BU96LMAB)) ^707486268 - In terms of equations, if a system has two equations, and both equations describe the same line, the system will have an infinite continuum of solutions. Such systems are called indeterminate. ([Page 52](zotero://open-pdf/library/items/ZQ5NT2VZ?page=75&annotation=V9CXPC7X)) ^707486269 - Equations that represent the same hyperplane, even with different coefficients, are called linearly dependent. ([Page 52](zotero://open-pdf/library/items/ZQ5NT2VZ?page=75&annotation=SP95Y2IP)) ^707486270 - If there are as many variables as there are linearly independent equations, the system is called well-specified or well-defined. ([Page 53](zotero://open-pdf/library/items/ZQ5NT2VZ?page=76&annotation=28NNSYHN)) ^707486271 - When there are more equations than variables, the system is called overspecified, overconstrained, or overdetermined. ([Page 53](zotero://open-pdf/library/items/ZQ5NT2VZ?page=76&annotation=NIMWVEZG)) ^707486272 - If a system has more variables than equations, it’s called underspecified, underconstrained, or underdetermined. ([Page 55](zotero://open-pdf/library/items/ZQ5NT2VZ?page=78&annotation=X4DH2CL5)) ^707486273 - Symbolic computation is relatively slow, however. We can solve systems of a million equations numerically, but symbolically, it takes forever to solve even an 8 × 8 system. ([Page 55](zotero://open-pdf/library/items/ZQ5NT2VZ?page=78&annotation=M5CZ7UNJ)) ^707486274 - The point is getting closer to all the points of the top line, including the point of the solution. Because the point of solution belongs to both lines by definition, simply projecting the initial point back and forth moves it closer to the point of solution (figure 3.7). ([Page 56](zotero://open-pdf/library/items/ZQ5NT2VZ?page=79&annotation=T2AR7X9C)) ^707486275 - Another term that’s closely associated with convergence is stability. Stability is the ability of the algorithm not to accumulate an error as it goes, which is extremely important for iterative algorithms. ([Page 60](zotero://open-pdf/library/items/ZQ5NT2VZ?page=83&annotation=NMJT5GWP)) ^707486276 - Generally, to solve an N-dimensional hyperplane intersection, we have to solve N (N–1)-dimensional hyperplane intersections first. And each (N–1)-dimensional problem implies solving N–1 (N–2)-dimensional ones until we get down to solving a lot of 1-dimensional problems, which are trivial. ([Page 61](zotero://open-pdf/library/items/ZQ5NT2VZ?page=84&annotation=NDH6V56H)) ^707486277 - To sum things up, we can safely multiply any equation by a nonzero number; we can add any equation to another equation, which also implies subtraction; and we can make any two equations swap their places in a system. ([Page 68](zotero://open-pdf/library/items/ZQ5NT2VZ?page=91&annotation=Q4L3DWHZ)) ^707486278 - Another method close in heart to Gaussian elimination is LU-decomposition. LU stands for lower-upper, and it indeed decomposes a matrix into a product of lower-triangular and upper-triangular forms. Sometimes, it’s also called factorization because these matrices work as factors or multipliers of the source one. ([Page 73](zotero://open-pdf/library/items/ZQ5NT2VZ?page=96&annotation=7MIYWCFP)) ^707486279 - LU-decomposition may be used not only to solve linear equations, but also to find inverse matrices. ([Page 73](zotero://open-pdf/library/items/ZQ5NT2VZ?page=96&annotation=SC46RY7R)) ^707486280 - Although even direct algorithms bring in some computational error, iterative ones are all about changing computational error for speed. They make sense if you have a lot of equations and need to solve them fast—not necessarily accurately, but fast. ([Page 75](zotero://open-pdf/library/items/ZQ5NT2VZ?page=98&annotation=UCWK5FVP)) ^707486281 - Popular iterative methods such as Jacobi and Gauss-Seidel are tailored to work with diagonally dominant matrices. ([Page 75](zotero://open-pdf/library/items/ZQ5NT2VZ?page=98&annotation=YMSRULEQ)) ^707486282 - So instead of calling some numeric solver for a 2 × 2, 3 × 3, or 4 × 4 system, solve it symbolically, so that the solution isn’t specific numbers, but formulas that work for any input, and use the solution instead of the function call. I don’t suggest that you solve the system manually; you can use SymPy to do that. SymPy is the library that does your math for you. Specify the equations you want to solve symbolically, and run solve. SymPy will turn your equations into a solution, a bit like Gaussian elimination does, and will even translate the symbolic solution into the language of your choice. ([Page 76](zotero://open-pdf/library/items/ZQ5NT2VZ?page=99&annotation=ZMGZKLLF)) ^707486283 - The symbolic solution grows in both length and time by the factorial. Yes, symbolic solvers also have O(N!) complexity. Also, turned into code, the solution accumulates more computational error with every new dimension. These two things make this SymPy-based approach impractical for any system larger than 4 × 4. ([Page 76](zotero://open-pdf/library/items/ZQ5NT2VZ?page=99&annotation=HZT25DKW)) ^707486284 - Geometric transformations, projective space, and homogeneous coordinates are associated concepts that not only enable, but also explain one another. ([Page 86](zotero://open-pdf/library/items/ZQ5NT2VZ?page=109&annotation=PWAEHVYM)) ^707486285 - Unless the domain and codomain are deliberately restricted, the transformation concerns every point in space, so it transforms the whole space. Even if we transform some specific object, and we’re doing that by applying the transformation to each of its points, the transformation itself still describes how all the space changes. ([Page 87](zotero://open-pdf/library/items/ZQ5NT2VZ?page=110&annotation=AH9QI8Q3)) ^707486286 - Simply by incrementing our parameter t, we made a square go in circles. The concept of parametric transformation is the key to animation. ([Page 88](zotero://open-pdf/library/items/ZQ5NT2VZ?page=111&annotation=ADVQ2C56)) ^707486287 - A linear transformation is a transformation in which every new coordinate is a linear combination of old coordinates. ([Page 94](zotero://open-pdf/library/items/ZQ5NT2VZ?page=117&annotation=VMZDBKGD)) ^707486288 - The linear transformation retains parallelism, and it always transforms the zero point into itself. It’s also symmetrical regarding both the x and y axes, but to see this effect, you need a symmetrical object to transform (figure 4.12). ([Page 96](zotero://open-pdf/library/items/ZQ5NT2VZ?page=119&annotation=V83FM5Q3)) ^707486289 - This operation is called affine transformation ([Page 98](zotero://open-pdf/library/items/ZQ5NT2VZ?page=121&annotation=IYZMRTMY)) ^707486290 - Bilinear transformation generalizes rotation, translation, and scale—all the affine transformations. But it doesn’t generalize itself to 3D as nicely as a projective transformation does. ([Page 103](zotero://open-pdf/library/items/ZQ5NT2VZ?page=126&annotation=HX9LXPKF)) ^707486291 - But the points where wp = 0 still exist—not in Euclidean space, but in projective space. They extend our Euclidean space because they complement it with an additional shell of points. These non-Euclidean points also make a lot of computations easier, but to understand them, we’ll have to massage our imagination a little. ([Page 105](zotero://open-pdf/library/items/ZQ5NT2VZ?page=128&annotation=NLVLQXM9)) ^707486292 - This belt is (xp, yp, 0). It doesn’t convert to Euclidean space, because there are no such points in that space. Every point from this belt is farther from the zero point than any point in Euclidean space. ([Page 105](zotero://open-pdf/library/items/ZQ5NT2VZ?page=128&annotation=BFVUGRQS)) ^707486293 - This way of notation, supplying a denominator to a coordinate tuple, is called homogeneous or projective coordinates. ([Page 106](zotero://open-pdf/library/items/ZQ5NT2VZ?page=129&annotation=AF4NM798)) ^707486294 - Don’t worry; all real-world transformation matrices are invertible. ([Page 113](zotero://open-pdf/library/items/ZQ5NT2VZ?page=136&annotation=MDT4VQLV)) ^707486295 - But let’s look into a trick we can use to make the computation faster. We can use the cofactor transposition instead of the real matrix inversion. ([Page 114](zotero://open-pdf/library/items/ZQ5NT2VZ?page=137&annotation=PIZZUGAS)) ^707486296 - An i-j minor is a matrix without i-row and j column. ([Page 115](zotero://open-pdf/library/items/ZQ5NT2VZ?page=138&annotation=FVA6KSZR)) ^707486297 - Suppose that we want to probe a lot of points against a few triangles as fast as possible and that we have some free preprocessing time. One way to go would be to turn each triangle into a convenient transformation in its own basis and then apply this transformation to each point we want to check (figure 4.22). ([Page 120](zotero://open-pdf/library/items/ZQ5NT2VZ?page=143&annotation=KAVKPU8B)) ^707486298 - In SymPy, the differentiation utility is called diff. ([Page 135](zotero://open-pdf/library/items/ZQ5NT2VZ?page=158&annotation=6QJQLT9Q)) ^707486299 - A tangent vector of a parametric curve is (fx(t)', fy(t)'). ([Page 139](zotero://open-pdf/library/items/ZQ5NT2VZ?page=162&annotation=WDDP2FLM)) ^707486300 - What you have to keep in mind is that for a parametric curve, the continuous curvature implies the continuous second derivatives. ([Page 142](zotero://open-pdf/library/items/ZQ5NT2VZ?page=165&annotation=8TQP38ZW)) ^707486301 - The nth coefficient of a polynomial is the last coefficient of its nth degree divided by n factorial. ([Page 166](zotero://open-pdf/library/items/ZQ5NT2VZ?page=189&annotation=SRYZH29J)) ^707486302 - So we can approximate a function by taking its derivatives in 0 and turning these derivatives into a polynomial. This approach is called the Maclaurin series. ([Page 170](zotero://open-pdf/library/items/ZQ5NT2VZ?page=193&annotation=SJ5RABNL)) ^707486303 - When we take the derivatives in some other point than 0, the power series is called the Taylor series ([Page 170](zotero://open-pdf/library/items/ZQ5NT2VZ?page=193&annotation=MTQRV3BE)) ^707486304 - The Visualize It website has an interactive plot for the least-squares approximation called Polynomial Regression at http://mng.bz/Jl4V. ([Page 175](zotero://open-pdf/library/items/ZQ5NT2VZ?page=198&annotation=A4ZBTPH4)) ^707486305 - Generally, a set of N points may be interpolated by a polynomial of a degree no less than N–1. ([Page 180](zotero://open-pdf/library/items/ZQ5NT2VZ?page=203&annotation=7RRLK7KX)) ^707486306 - The matrix on the left is called the Vandermonde matrix. It’s a matrix made of “the polynomial goes through a point” equations. ([Page 181](zotero://open-pdf/library/items/ZQ5NT2VZ?page=204&annotation=97H4HJ5R)) ^707486307 - Lagrange interpolation is also polynomial and also results in an N–1-degree polynomial for N points, so it brings nothing new to the picture. ([Page 187](zotero://open-pdf/library/items/ZQ5NT2VZ?page=210&annotation=M4C3R36T)) ^707486308 - NURBS is an acronym that stands for “nonuniform rational basis spline,” and this kind of spline generalizes Bézier curves, giving us many more options to control the properties and shape of the modeled curve. ([Page 204](zotero://open-pdf/library/items/ZQ5NT2VZ?page=227&annotation=KURL6E4E)) ^707486309 - The tangent of the line’s angle toward the x-axis is the derivative of the polynomial at a point. ([Page 205](zotero://open-pdf/library/items/ZQ5NT2VZ?page=228&annotation=SP5QNFI5)) ^707486310 - The subs here stands for substitution: it substitutes a specific numeric value for the parameter x. This substitution turns a parametric symbolic equation into a numeric one. ([Page 210](zotero://open-pdf/library/items/ZQ5NT2VZ?page=233&annotation=NNWW4CEH)) ^707486311 - Now let’s add some smoothness. Smoothness comes from the continuity of the first derivative, which in our case means that the derivative should be exactly 0 at the and . ([Page 210](zotero://open-pdf/library/items/ZQ5NT2VZ?page=233&annotation=CW9QHLCI)) ^707486312 - A polynomial parametric curve, as you can guess, is a parametric curve with polynomial per-coordinate functions. ([Page 216](zotero://open-pdf/library/items/ZQ5NT2VZ?page=239&annotation=DKY6V8M8)) ^707486313 - Now, instead of computing them all from the “curve goes through the point” equations, let’s get half of them from the “curve has a given tangent vector at a point” equations. ([Page 218](zotero://open-pdf/library/items/ZQ5NT2VZ?page=241&annotation=CGP8QHCT)) ^707486314 - We can add degrees and have the properties we want until the polynomial becomes too large and unpredictable due to the Runge phenomenon. ([Page 220](zotero://open-pdf/library/items/ZQ5NT2VZ?page=243&annotation=5TRARI5M)) ^707486315 - To avoid that unpredictability, we should split our target curve into a set of smaller ones and conjoin them back to back concerning their tangent vectors based on the first derivative (figure 7.9). ([Page 221](zotero://open-pdf/library/items/ZQ5NT2VZ?page=244&annotation=STVFDWA8)) ^707486316 - In practice, however, curves with polynomials often go by the name Bézier. ([Page 226](zotero://open-pdf/library/items/ZQ5NT2VZ?page=249&annotation=75NR4358)) ^707486317 - Bézier curves are parametric curves. They’re also produced by a pair (in 2D) or a triplet (in 3D) of per-coordinate functions. Moreover, in classical Bézier curves, the per-coordinate functions are also polynomial. But instead of finding the polynomials’ coefficients explicitly, we build up the polynomials from basis functions, as like we did with Lagrange interpolation (chapter 6). ([Page 226](zotero://open-pdf/library/items/ZQ5NT2VZ?page=249&annotation=DE6LFEVZ)) ^707486318 - The function consists of two basis polynomials. The first is 1 – t, and the second is t. We make a formula for a specific first-degree Bézier function by multiplying the first basis polynomial by the first value, y1, and the second basis polynomial by multiplying by the second value, y2. ([Page 226](zotero://open-pdf/library/items/ZQ5NT2VZ?page=249&annotation=LB5WN9A8)) ^707486319 - So the basis polynomials for the first-degree Bézier function are exactly the same as for the Lagrange interpolation! ([Page 228](zotero://open-pdf/library/items/ZQ5NT2VZ?page=251&annotation=MM8PLGYN)) ^707486320 - The property is “the sum of all the basis functions in a Bézier formula is always 1.” ([Page 228](zotero://open-pdf/library/items/ZQ5NT2VZ?page=251&annotation=K4R4H62P)) ^707486321 - Now let’s multiply (a + b) by . . . (a + b). The product will still be 1 because we essentially multiply 1 by 1. The result of this multiplication, then, is a2 + ab + ba + b2, or because ab = ba, a2 + 2ab + b2. Putting the t back into the formula, we’ll get the basis polynomials for the seconddegree Bézier formula ([Page 228](zotero://open-pdf/library/items/ZQ5NT2VZ?page=251&annotation=RTXJK8NN)) ^707486322 - B2(t) = (1 – t)2y1 + 2(1 – t)ty2 + t 2y3 ([Page 228](zotero://open-pdf/library/items/ZQ5NT2VZ?page=251&annotation=9564VA65)) ^707486323 second-degree or quadratic Bézier formulas - Note that the vectors from point 1 to point 2, and from point 3 to point 4 are collinear to the tangent vectors. Also, a simple proportion makes Bézier points into tangent vectors for explicit polynomial modeling, and vice versa. The proportion is three. Yes, it’s that simple. The tangent vectors are three times the point differences (figure 7.17). ([Page 230](zotero://open-pdf/library/items/ZQ5NT2VZ?page=253&annotation=KMQ9N97V)) ^707486324 - A Bézier function with weights is called a rational Bézier function. These weights give us additional control of the function and, consequently, the shape of the curve. ([Page 231](zotero://open-pdf/library/items/ZQ5NT2VZ?page=254&annotation=ELJFPM2I)) ^707486325 - NURBS stands for “nonuniform rational basis spline.” ([Page 233](zotero://open-pdf/library/items/ZQ5NT2VZ?page=256&annotation=HMBBYZSD)) ^707486326 - With NURBS, parametric distances between points are set by a special knot vector, an array of arbitrary parameter values in which every pair of adjacent values stands for a segment or, if the values are equal, for skipping a segment. ([Page 235](zotero://open-pdf/library/items/ZQ5NT2VZ?page=258&annotation=BYQXJXNP)) ^707486327 - One way to build a NURBS surface is to use de Boor’s algorithm. This algorithm doesn’t compute the basis polynomials explicitly; instead, it evaluates them by using a recursive relation. ([Page 236](zotero://open-pdf/library/items/ZQ5NT2VZ?page=259&annotation=GMNFTAZA)) ^707486328 - Now, a distance function is a function that for any point in space, both inside the body and outside, tells how far the nearest point of the body’s surface is. ([Page 311](zotero://open-pdf/library/items/ZQ5NT2VZ?page=334&annotation=834E84T3)) ^707486329 #qa What's an SDF? 对于空间中的**任何点**，无论是物体内部还是外部，都会返回到该物体表面最近点的距离。 - In Python, an SDF is an expression. ([Page 313](zotero://open-pdf/library/items/ZQ5NT2VZ?page=336&annotation=TR2CL95F)) ^707486330 #qa How to program SDFs? SDF is a function for any point in the space. - With boundary representation, we model only the boundary of a body or shape. In 2D, we model a set of contours that represents the shape’s border. In 3D, we model a set of surfaces that represents the border of a body. ([Page 341](zotero://open-pdf/library/items/ZQ5NT2VZ?page=364&annotation=UMKTDEKT)) ^707486331 - But if you write the cube’s vertices first and then represent triangles as triplets of vertices’ indices, you need only 8 × 3 + 12 × 3 = 60 numbers. See, even for a simple model, this representation is already proving to be economical. ([Page 347](zotero://open-pdf/library/items/ZQ5NT2VZ?page=370&annotation=5KQELMHG)) ^707486332 - In practice, we often employ another data representation for mesh processing. This new representation, called a half-edge data model, stores all the mesh not as triangles, but as oriented triangle edges. ([Page 348](zotero://open-pdf/library/items/ZQ5NT2VZ?page=371&annotation=6L7JQR4W)) ^707486333 - The half-edge model contains more redundant data than vertices and triangles alone, so it’s not an economical way to store meshes. It’s more fitting for processing purposes, though. ([Page 349](zotero://open-pdf/library/items/ZQ5NT2VZ?page=372&annotation=KD6WXFBP)) ^707486334 - That’s why we have a paradox in the triangle world: as hardware gets better, the software seems to get worse. With better hardware, we’re ready to process more and more detailed models. But the same software that was great for the 1990s and early 2000s now fails far more often. ([Page 351](zotero://open-pdf/library/items/ZQ5NT2VZ?page=374&annotation=HZC9HUIX)) ^707486335 - At some point, converting a few meshes to SDFs, doing the operations, and converting the result back becomes a feasible alternative to doing everything on meshes alone. ([Page 352](zotero://open-pdf/library/items/ZQ5NT2VZ?page=375&annotation=LPMHXCAB)) ^707486336 - With this approach, we have to compromise the precision again because the twoway mesh-SDF-mesh conversion isn’t exact. ([Page 353](zotero://open-pdf/library/items/ZQ5NT2VZ?page=376&annotation=8AY6J6YL)) ^707486337 - Marching cubes were first published in 1987 by William E. Lorensen and Harvey E. Cline as a way to visualize data obtained with computer tomography (CT). ([Page 354](zotero://open-pdf/library/items/ZQ5NT2VZ?page=377&annotation=I8E4HLFH)) ^707486338 #reference - Conceptually, contouring is a simple task. What we want to do is find the contour segments that segregate the positive values of SDF from the negative ones. ([Page 356](zotero://open-pdf/library/items/ZQ5NT2VZ?page=379&annotation=UMRG5H4W)) ^707486339  - So let’s put the circle in a fine grid and in every grid cell border put one of the following ([Page 356](zotero://open-pdf/library/items/ZQ5NT2VZ?page=379&annotation=C2LXIYES)) ^707486340 #qa How to find the contour of an SDF? Use a grid and compute the SDF for the center points of each grid cell. Draw the line between cells having positive distance with the ones having negative distance. - So using the SDF values in vertices, we can make an educated guess about exactly where the curve intersects the edge by interpolating the SDF values linearly ([Page 358](zotero://open-pdf/library/items/ZQ5NT2VZ?page=381&annotation=3R4EL2K2)) ^707486341 - Then we’ll put line segments where the SDF changes its sign, almost as we did before. Previously, though, we put line segments from edge to edge wherever both edges have different SDF signs on their vertices. ([Page 360](zotero://open-pdf/library/items/ZQ5NT2VZ?page=383&annotation=LSZU8FUC)) ^707486342 - This example is a gradient of a function. It’s a vector that shows the direction in which the function grows most at a point. ([Page 362](zotero://open-pdf/library/items/ZQ5NT2VZ?page=385&annotation=I2P5BMRK)) ^707486343 - Now that we know both the direction and the distance, we can move the vertices and make ourselves a nice smooth contour (figure 11.23). ([Page 362](zotero://open-pdf/library/items/ZQ5NT2VZ?page=385&annotation=AKJGEZKJ)) ^707486344 Move vertices by gradient - But the true power of this particular algorithm comes not from making curves smooth, but from the ease of making corners sharp. ([Page 362](zotero://open-pdf/library/items/ZQ5NT2VZ?page=385&annotation=CXZ9LMVD)) ^707486345 - I like this algorithm because it shows how different concepts, each of which is hard to learn by itself, combine into a practical and exciting thing. I’m talking about smooth contouring. ([Page 365](zotero://open-pdf/library/items/ZQ5NT2VZ?page=388&annotation=YMHHNZGE)) ^707486346 - But because we know that SDF is a distance function, we know exactly how far each vertex is from the expected curve. The value of SDF in each vertex is exactly the approximation error. Can we reduce this error, then? Sure! Let’s shift every vertex by its own error value toward the direction inverse to the SDF’s gradient. We already did this with dual contouring. ([Page 366](zotero://open-pdf/library/items/ZQ5NT2VZ?page=389&annotation=LPGBXPN3)) ^707486347 - The gradient says exactly how the SDF changes at a point. Its partial derivatives correspond to the function’s change by x and by y. We can extract this information to build a parametric cubic curve from each line segment. ([Page 367](zotero://open-pdf/library/items/ZQ5NT2VZ?page=390&annotation=PPWAMPHX)) ^707486348 - The term voxel means a pixel that has a volume: volume pixel, vo-xel, voxel. ([Page 374](zotero://open-pdf/library/items/ZQ5NT2VZ?page=397&annotation=RIWU9HDV)) ^707486349 - Simply put, a tomograph scans your body and captures a lot of 2D x-ray images; then a computer turns all those images into a single 3D image, in which every voxel contains a value in special units estimating how much of the x-ray radiation is being absorbed by tissue in that voxel. ([Page 375](zotero://open-pdf/library/items/ZQ5NT2VZ?page=398&annotation=USCKXCTZ)) ^707486350 - Sophisticated computer vision algorithms can tell bone from other tissue, and neural networks can be trained to see skulls everywhere, but in practice, none of these systems has 100% accuracy. ([Page 378](zotero://open-pdf/library/items/ZQ5NT2VZ?page=401&annotation=YILQ5NYJ)) ^707486351 - The problem of finding an object on an image, or splitting the image into several objects, is called segmentation. ([Page 379](zotero://open-pdf/library/items/ZQ5NT2VZ?page=402&annotation=MCGDCBNU)) ^707486352 - This approach is called segmentation by threshold. The range of HU in which we’re expecting to see bone tissue is our threshold. ([Page 379](zotero://open-pdf/library/items/ZQ5NT2VZ?page=402&annotation=63R5PZCH)) ^707486353 - Practical example: Image vectorization ([Page 388](zotero://open-pdf/library/items/ZQ5NT2VZ?page=411&annotation=SQZFHJVW)) ^707486354 #similar See also 11.4 Smooth contouring