Question

1.1 Describe the Marching Cubes algorithm using pseudo-code. What are potential issues of Marching Cubes.
(I need pseudo code explaination)

Answer 1

solution:

given data:

1.1): Marching Cubes algorithm using pseudo-code:

The pseudocode below describes an application of Marching Cubes for representing the volumetric union, intersection, or difference of two closed triangular meshes.

For clarity, one simple optimization was left out of the ISINSIDE() subroutine: The triangles of the surface A can be persistently associated with cubes on a uniform grid, and raytesting can first identify the grid cubes that intersect the ray before testing the triangles associated with each cube. This eliminates the need to test many triangles.

ALGORITHM: Marching Cubes

Input: Closed surface A

Input: Closed surface B

Input: CSG_OP, one of {UNION, INTERSECTION,DIFFERENCE}

Input: Resolution r

let L be an axis-aligned lattice of cubes with sidelength r

let T be an empty list of triangles

for each lattice point p in L do

let pA = ISINSIDE(A, p, r)

let pB = ISINSIDE(B, p, r)

let pOUT = CSG_STATE(CSG_OP, pA, pB)

end for

for each lattice segment e in L do

let points p1 and p2 be endpoints of e

if (p1OUT ≠ p2OUT then)

set edge point p0 = INT_POINT(CSG_OP, A, B, p1, p2)

end if

end for

for each cube c in L do

let P = {p0, p1, . . . , p7} be corners of c

let E = {e0, e1, . . . , } be edge points of any segment of c

let triangles t = LOOKUP(P, E)

append t to T

end for

Output: T, the output boundary surface

ISINSIDE(A, p, r)

Input: Closed surface A

Input: point p

let R be a randomly oriented ray originating at p

let L be an axis-aligned lattice of cubes with sidelength r

let pointList be an empty list of points

for each triangle t in A that intersects R do

let pi be the point of intersection between t and R

if pi is not already an element of pointList then

add pi to pointList

end if

end for

if the size of pointList is even then

Output: false, p is outside A

else

Output: true, p is inside A

end if

CSG_STATE(CSG_OP, pA, pB)

Input: CSG_OP, one of {UNION, INTERSECTION,DIFFERENCE}

Input: pA, true if p is inside surface A, false otherwise.

Input: pB, true if p is inside surface B, false otherwise.

let the bool result = false

if CSG_OP = UNION and pA = true or pB = true then

set result = true

end if

if CSG_OP = INTERSECTION and pA = true and pB = true then

set result = true

end if

if CSG_OP = DIFFERENCE and pA = true and pB = false then

set result = true

end if

Output: result

INT_POINT(CSG_OP, A, B, p1, p2)

Input: CSG_OP, one of {UNION, INTERSECTION,DIFFERENCE}

Input: the surfaces A, B

Input: p1, p2, endpoints of the lattice segment e.

Either p1 is p2 is inside the output surface.

Assume without loss of generality that p1 is inside the output surface.

let pa be the point where e intersects A

let pb be the point where e intersects B

if either pa or pb does not exist then

Output: pb or pa, the one that does exist.

else

if CSG_OP = UNION then

Output: pa or pb, whichever is further from p1.

end if

if CSG_OP = INTERSECTION or DIFFERENCE then

Output: pa or pb, whichever is closer to p1.

end if

LOOKUP(P, E)

Input: P, the inside/outside state of the 8 lattice cube corners.

Input: E, intersection points on lattice segments of the cube.

Output: Triangles t that approximate the output surface in the cube.

Potential issues of Marching Cubes:

1. Creates mesh which can be highly over-sampled (requires Decimation) and contain bad triangle shapes (requires Mesh Optimization / Re-Meshing).

2. Linear interpolation of distance values approximates smooth surfaces: Sharp features within cells are lost.

3. Aliasing artifacts due to alignment of the voxel grid. Increasing voxel resolution only reduces the size of the artifacts but they never go away.

please give me thumb up