Development of a Constructive
Solid Geometry Algorithm

Michael Twardos

Electronic Arts

Graphics

Internet Media

Animated Movies

Video Games ... of course!

Content is becoming 1) more complex and 2) more 3D!

Import["/Users/miketwardos/Desktop/Talk/RealTalk/neospore-in_screen001_wm695_screen.jpg"]

Vestibulum ornare, massa non auctor porta, erat elit varius lacus, a posuere nibh est ut pede. Fusce quis dolor. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Mauris scelerisque erat vel elit.

Graphics Tools

Designers & Engineers

AutoCAD

Solid Works

Artists

Maya

3D Studio Max

How do these tools work?

Import["/Users/miketwardos/Desktop/7828pic.jpg"]

Constructive Solid Geometry

Boolean Operations on Simple Objects (Primitives)

Import["/Users/miketwardos/Desktop/Talk/RealTalk/677px-Csg_tree.png"]

How do I build It?

How to Approach the Problem

Construct a primitives of the form

polyhedrons = {polygons} = {points, edges, normal, info (in or out)}

For each primitive, cut each of its polygons, by each of the polygons in the cutting Polygon

Manipulate[cutter=tetrahedron[{0,0,0.2},1,0];
polyZ=tetrahedron[{1-position,-0.2,0},1,0.4];
Graphics3D[{Opacity[0.5],Red, Polygon[First[#]]&/@cutter,Blue,Polygon[First[#]]&/@polyZ , If[ShowPolygons,{Opacity[1],Polygon[First[polyZ[[polygons]]]]},Green], If[ShowPolygons,{Red,Opacity[1],Polygon[First[cutter[[cuttingPolygons]]]]},Green]},ImageSize->Medium,Boxed->False ],{position,0,2},{{ShowPolygons,False}, {True, False}},{{cuttingPolygons,3},Range[Length[cutter]]},{{polygons,2}, Range[Length[polyZ]]}]

Step1: Determine if Cutter Crosses Polygon Plane -> Get Plane Points

polyP={{{4.8,4.8,0},{5.8,4.8,0},{5.3,5.6,0}},{0.`,0.`,-1.`},{{1,2},{2,3},{3,1}},{}};
Manipulate[cutter={{{5.5+x,5+y,2-z},{5.5+x,5+y,1-z},{5+x,5.8+y,2-z}},{0.8660254037844385`,0.5`,0.`},{{1,2},{2,3},{3,1}},{}};
PlanePoints=DetermineCut[cutter[[1]],cutter[[3]]];
Graphics3D[{Green,Black,Sphere[#,0.05]&/@PlanePoints,
Red, Polygon[First[cutter]],Opacity[1],Blue,Polygon[First[polyP]]},ImageSize->Medium ],{z,0,3}, {x,-1,1}, {y,-1,1}]

Step 2: Determine if Plane Points are Inside Polygon

polygonA={{0,0,0},{1,1,0},{2,0,0}};
edges={{1,2},{2,3},{3,1}};Manipulate[Graphics[{Text[Style[DetermineIfPointInPoly[{pt[[1]],pt[[2]],0},polygonA,edges],Large],{0,1.5}],Blue,EdgeForm[Directive[Thick]],Polygon[#[[1;;2]]&/@polygonA],Black,Disk[{pt[[1]],pt[[2]]},0.05]}, ImageSize->Medium],{{pt,{-0.1,-0.1},{3,2}}, Locator}]

testPoint={1,1.65};
pts={{1.25,1},{2,2},{2.75,1}};
Graphics[{Blue,EdgeForm[Directive[Thick]],
Polygon[pts],Text[Style["?",Large],testPoint+{0,0.2}], Black, Disk[testPoint,0.1]
}, Axes->True, PlotRange->{{0.5,3.5},{0.5,2.5}}]

pts={{1.25,1},{2,2},{2.75,1}};
Graphics[{Blue,EdgeForm[Directive[Thick]],
Polygon[pts], Black, Text[Style["Not Inside",Large],testPoint+{0,0.2}],
Purple, Disk[{1,1.65},0.1],Black, Thick, 
Line[{testPoint,testPoint+{3,0}}],Red,Disk[{1.75,1.65},0.1],Disk[{2.25,1.65},0.1]
}, Axes->True, PlotRange->{{0.5,3.5},{0.5,2.5}}]

testPoint2={2,1.45};
pts={{1.25,1},{2,2},{2.75,1}};
Graphics[{Blue,EdgeForm[Directive[Thick]],
Polygon[pts],Black, Text[Style["Inside",Large],testPoint2-{0,0.3}],
Purple, Disk[testPoint2,0.1],Black, Thick, 
Line[{testPoint2,testPoint2+{3,0}}],Red,Disk[{2.4,1.45},0.1]
}, Axes->True, PlotRange->{{0.5,3.5},{0.5,2.5}}]

Step 3: Determine Where Cutter Cuts Polygon

polyP={{{4.8,4.8,0},{5.8,4.8,0},{5.3,5.6,0}},{0,0,-1},{{1,2},{2,3},{3,1}},{}};
polyEdges={{1,2},{2,3},{3,1}};
Manipulate[cutter={{{5.5+x,5+y,2-z},{5.5+x,5+y,1-z},{5+x,5.8+y,2-z}},{0.8,0.5,0},{{1,2},{2,3},{3,1}},{}};
PlanePoints=DetermineCut[cutter[[1]],cutter[[3]]];
If[TrueQ[PlanePoints!= {}],
pointsInPolyQ=DetermineIfPointInPoly[#,polyP[[1]],polyEdges]&/@PlanePoints;
ptsAre=If[MemberQ[pointsInPolyQ,"Point in Poly"],
Select[{DetermineIntersect2[{polyP[[1]][[#]], PlanePoints}],#}&/@polyEdges,#[[1]]=!=False&],
Select[{DetermineIntersect4[{polyP[[1]][[#]], PlanePoints}],#}&/@polyEdges,#[[1]]=!=False&]];
pts=#[[1]]&/@ptsAre, pts={}];
Graphics3D[{Green, If[t,Sphere[#,0.05]&/@pts,Green],Black,Sphere[#,0.05]&/@PlanePoints,
Red, Polygon[First[cutter]],Opacity[1],Blue,Polygon[First[polyP]]},ImageSize->Medium ],{z,0,3}, {x,-1,1}, {y,-2,1},{{t,False, "Show Polygon Cut Points"},{True,False}}]

Example: Cut One Poly by One Cutter

colRules={"Outside"->Purple, "Inside"->Green};cut1={{{4.5,5,5},{5.5,5,6},{5.5,5,5}},{0,-1,0},{{1,2},{2,3},{3,1}},{}};Manipulate[polyPiece={{{y,4.8,5.5`},{y+1,4.8,5.5},{y+0.5,5.6,5.5}},{0,0,-1},{{1,2},{2,3},{3,1}},{}};
cuts=Flatten[cutPolys[#,Most[cut1]]&/@{polyPiece},1];Graphics3D[{Red,Polygon[First[cut1]],Opacity[1],Blue,If[Length[cuts]>1,{First[Last[#]]/.colRules,Polygon[First[#]]}&/@cuts,Polygon[First[#]]&/@cuts]}, Axes->False, Boxed->False, ImageSize->Medium],{y,3,6}]

Example 2: Adding Another Cutter

cut2={{{5.5`,5.`,5},{5.5`,5.`,6},{5.`,5.866025403784438`,5}},{0.8660254037844385`,0.5`,0.`},{{1,2},{2,3},{3,1}},{}};Manipulate[polyPiece={{{y,4.8,5.5`},{y+1,4.8,5.5},{y+0.5,5.6,5.5}},{0.`,0.`,-1.`},{{1,2},{2,3},{3,1}},{}};
cuts=Flatten[cutPolys[#,Most[cut2]]&/@Flatten[cutPolys[#,Most[cut1]]&/@{polyPiece},1],1];Graphics3D[{Opacity[0.8],Red,Polygon[First[cut2]], Polygon[First[cut1]],Opacity[1],Blue,If[Length[cuts]>1,{Last[Complement[Last[#]]]/.colRules,Polygon[First[#]]}&/@cuts,Polygon[First[#]]&/@cuts]},ImageSize->Large,  Axes->False],{{y,5.5},4.8,6}]

The Rest of The Code

Looking out for special cases of cutters and polygons. For example

{Graphics3D[{Red,Polygon[{{0,0,0},{0.7,1,0},{1.4,0,0}}],Opacity[1],Blue,Polygon[{{0,0,0},{0.7,1,0},{0,0,1}}]}, Boxed->True, ImageSize->Medium],Graphics3D[{Opacity[0.9],Red,Polygon[{{0,0,0},{0.7,1,0},{1.4,0,0}}],Blue,Polygon[{{0,1,0},{1,0,0},{1.4,1.2,0}}]}, Axes->False, Boxed->False, ImageSize->Medium]}

Primitives

Manipulate[Graphics3D[{Opacity[0.8],
Polygon[First[#]]&/@#
},Boxed->False, Axes->False]&/@{tetrahedron[{8,5.1,4.9},3,q],
cylinder[{4.55,8.0,4},2,2,q], cube[{5.6,5,5.5},1,q]},{q,0,2*Pi}]

Cube Operations

Manipulate[{Graphics3D[{Opacity[0.8],Thick,
Polygon[First[#]]&/@((booNot[cube[{3.9,4.4,5},1.9, 0],cube[{x,y,5.5},1.9, 0]])[[1]])
}, Boxed->False, ImageSize->Medium],Graphics3D[{Opacity[0.6],Thick,
Polygon[First[#]]&/@((booOr[cube[{3.9,4.4,5},1.9, 0],cube[{x,y,5.5},1.9,0]]))
}, Boxed->False, ImageSize->Medium]},{y,4.5,7.0},{x,4,7}]

"Cylinder" and Cube

Manipulate[{Graphics3D[{Opacity[0.6],Thick,
Polygon[First[#]]&/@((booOr[cylinder[{4.50,5.0,4},1,3,0],cube[{x,y,5.5},1.9,0]]))
}, Boxed->False,ImageSize->Medium],Graphics3D[{Opacity[0.6],Thick,
Polygon[First[#]]&/@((booNot[cylinder[{4.50,5.0,4},1,3,0],cube[{x,y,5.5},1.9,0]])[[1]])
}, Boxed->False, ImageSize->Medium]},{{x,5},4,6},{{y,5.2},4.5,6.0}]

Cylinder and Tetrahedron

Manipulate[{Graphics3D[{Opacity[0.8],Thick,
Polygon[First[#]]&/@((booAnd[tetrahedron[{4.50,5.0,6.7},3,0],cylinder[{x,y,5.5},1.5, 4,0]]))
}, Boxed->False, ImageSize->Medium], Graphics3D[{Opacity[0.8],Thick,
Polygon[First[#]]&/@((booOr[tetrahedron[{4.50,5.0,6.7},3,0],cylinder[{x,y,5.5},1.5, 4,0]]))
}, Boxed->False, ImageSize->Medium]},{{y,5.44},5,6},{{x,5.25},4.5,5.5}]

Manipulate[{Graphics3D[{Opacity[0.8],Thick,
Polygon[First[#]]&/@((booNot[tetrahedron[{4.50,5.0,5.7},2,0],cylinder[{x,y,5.5},1, 3,0]])[[1]])
}, Boxed->False, ImageSize->Medium],Graphics3D[{Opacity[0.8],Thick,
Polygon[First[#]]&/@((booNot[tetrahedron[{4.50,5.0,5.7},2,0],cylinder[{x,y,5.5},1, 3,0]])[[2]])
}, Boxed->False, ImageSize->Medium]},{y,5,6},{x,4.5,5.5}]