CSG rendering Booleans Space partitions CSG & BSP CSG expression/tree Positive form of a CSG tree Active zone Z of a primitive Classifying surfels Blist form Blister rendering A Jarek Rossignac http://www.gvu.gatech.edu/~jarek B C MAGIC MAGIC
E F D Georgia Tech, IIC, GVU, 2006 1 What is a polyloop L? A closed loop curve defined by a cyclically ordered set of control vertices It is convenient to have next (in) and previous (ip) functions for accessing them int vn =6; // number of control vertices pt[] P = new pt [vn]; // vertices of the control polyloop int in(int j) { if (j==vn-1) {return (0);} else {return(j+1);} }; // next vertex in control loop int ip(int j) { if (j==0) {return (vn-1);} else {return(j-1);} }; // previous vertex in control loop The user should be able to insert, delete, and move the control vertices and get a smooth curve J interpolating or approximating the polyloop L Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC J Georgia Tech, IIC, GVU, 2006
2 Concavity and inflection How to test whether corner (A,B,C) is a left turn? BCAB.left>0 A curve is convex when all corners are left turns or all corners are right turns CW: clockwise, CCW: counterclockwise Convention: we orient the curve ccw Some curves cannot be oriented (which?) An inflection edge joins a left and a right turn corner (example?) Concave vertices? Inflection edges? Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 3 Point-in-polygon test in 2D Given a polygon P and a point q in the plane of P, how would you test whether q lies inside P? Jarek Rossignac http://www.gvu.gatech.edu/~jarek
MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 4 Point-in-polygon test Algorithm for testing whether point q is inside polygon P in:=false; for each edge (a,b) of P { if (PinT(q,a,b,o)) in := !in; }; return in; b q o PinT(q,a,b,o) was studied earlier b q o Jarek Rossignac http://www.gvu.gatech.edu/~jarek a MAGIC MAGIC a Georgia Tech, IIC, GVU, 2006
5 XOR shading of a polygon in 2D AB is the set of points that lie in A or in B, but not in both AB := {p: pA != pB } Let A, B, C, N be primitives, then ABC N is the set of points contained in an odd number of these primitives AB := {p: (pA) XOR (pB) XOR (pC) XOR XOR (pN) } How to shade a polygon A in 2D: Given a polygon A, with edges E1, E2, En, let Ti denote the triangle having as vertices an arbitrary origin o and the two endpoints of Ei. The interior of A is T1T2T3 Tn If you ignore the cracks To shade A: E5 E4 E1 E3 E2P Initialize all pixels to be background Shade all the Ti using XOR Toggle status of each visited pixel Jarek Rossignac http://www.gvu.gatech.edu/~jarek oo MAGIC MAGIC Georgia Tech, IIC, GVU, 2006
6 Example of XOR polygon filling E1 P o E1 o o E3 o Jarek Rossignac o E5 E4 E3 E2 o http://www.gvu.gatech.edu/~jarek
o MAGIC MAGIC o Georgia Tech, IIC, GVU, 2006 7 Relation to ray-casting approach? A point p lies in a set A if a ray from p intersects the boundary of A an odd number of times If your ray hits a vertex or edge or is tangent to a surface, pick another ray We do the same thing. Look at an example in 2D. Here: Only edges E1, E2, E3 intersect the ray from p in the opposite direction to o Thus only triangles T1, T2, T3 contain p p o Ray from p p is in because it is contained in an odd number of triangles Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC
Georgia Tech, IIC, GVU, 2006 8 Convex sets and convex hulls A set S is convex if for any points a and b in S, the segment ab is in S. The convex hull H(S) of a set S is the smallest convex set containing S. Is it true that for a planar set S, H(S) is the union of all line segments ab with a and b in S? Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 9 Line arrangements in the plane N lines divide the plane into cells Convex 2d regions bounded by line segments (some unbounded) Assume lines are in general position no 2 are parallel, no 3 are coincident How many cells do we have? Do a few examples Establish a recursive formulation Solve it Remember the essence of your approach
L=1, C(1)=2 Jarek Rossignac L=2, C(2)=4 http://www.gvu.gatech.edu/~jarek L=3, C(3)=7 MAGIC MAGIC L=4, C(4)= Georgia Tech, IIC, GVU, 2006 10 Counting cells in line arrangements Obviously C(0)=1. For n>0, C(n)=C(n1)+n, because the line bounding the new half-space is intersected at most n points by previous lines and thus divided into at most n+1 segments. Each segment splits a previous cell into 2, and thus they all create at most n+1 new cells. The recursive formula yields C(n)=1+(1+2+3+4+5+n), which can be solved for C(n)=1+(n+1)n/2, using the fact that 1+2+3+4++n = n(n+1)/2 It may also be written as C(n)=(n2+n+2)/2. Indeed C(2)=1+3*(2/2)=4 and C(3)=7. Jarek Rossignac http://www.gvu.gatech.edu/~jarek
MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 11 How to identify a cell? How can we identify a cell? Label the lines: A, B, C How can you unambiguously reference a single cell? How many bits do you need for a cell name? What is the theoretically minimal number of bits? Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 12 How to specify collections of cells? Geometric: a point in each cell of the collection Any point will do Not convenient for drawing a cell Semi-algebraic In terms of inequalities as a Boolean combination of Half-spaces
Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 13 What is a half-space A half-space A separates space in 2 parts: A and !A (complement) Examples of algebraic half-spaces (polynomial inequality) A sphere, S(p,r)={q: ||pq||
Georgia Tech, IIC, GVU, 2006 14 Intersection of linear half-spaces C It is a convex set bounded by planar faces Some of the faces may be unbounded The intersection may be empty B How to test whether point q is inside? A How to test whether point q is on the boundary? C The intersection needs not be closed Complement of a closed half-space is open Each cell of an arrangement of lines B is the intersection of linear half-spaces, each half-sapce is bounded by one of the lines Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC
MAGIC Georgia Tech, IIC, GVU, 2006 A 15 BSP (Binary Space-partition Tree) Binary tree Each node Nj represents a convex cell Cj It is associated with a half space Hj The left child is associated with a cell Cj Hj The right child is associated with a cell Cj Hj A Leaves that are left children are in Other leaves are out B out B D C D C in out
in out A Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 16 How to test a point p against a BSP Start at the root When you reach a leaf return (leaf == leaf.parent.left) At an internal node If p in node.halfspace go left Else go right A B B D out
C D C in out in out A Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 17 BSP for back-to-front ordering of faces HSR = Hidden Surface Removal Currently done with z-buffer in contemporary hardware Previously done using painters algorithm (paint back-to-front) Back-to-front order is view dependent: use BSP to re-compute quickly BSP for back-to-front: At each internal node n store Half-space n.H Pointers to children n.L (in H) and n.R (out of H) List of front faces n.F in the boundary of H facing interior of H
List of back faces n.B in the boundary of H facing exterior of H Render (node n, viewpoint v) If (n==nil) RETURN; IF (v in n.H) {Render(n.R, v); Display(n.F); Render (n.L, v)} ELSE {Render(n.L, v); Display(n.B); Render (n.R, v)}; Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 18 Set theoretic Boolean operations 16 total, only 5 of interest union A+B = {s: s in A or s in B} complement !S = {s: s not in S} intersection AB = {s: s in A and s in B} difference xor Jarek Rossignac AB = {s: s in A and s not in B} AB =(A+B)AB http://www.gvu.gatech.edu/~jarek
MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 19 CSG (Constructive Solid Geometry) Set theoretical Boolean expression Has half-spaces as primitives Bounded solids: Blocks, spheres, cylinders, cones, tori Transformed by a rigid body motion Uses only union, intersection, and difference operators Priority: intersection higher than union and difference Example: (A+B)-(CD-E) is ((A+B)-((CD)-E)) B Write the simplest expression for the figure: A B C Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC A
C Georgia Tech, IIC, GVU, 2006 20 What is a CSG tree Consider a CSG expression: S=(AB)+(CD)(EF) It may be parsed into a binary tree Leaves correspond to primitive shapes Nodes represent Boolean operations Root represents solid defined by S root A Jarek Rossignac http://www.gvu.gatech.edu/~jarek E F B C D primitives MAGIC MAGIC
Georgia Tech, IIC, GVU, 2006 21 How to store a CSG expression Parsing a CSG expression yields a binary tree S = ((A+B)((C*D)E)), * stands for intersection - Store it as an table of nodes: Type: +, *, , prim Id Left: Id of left child node or of primitive Right: Id of right child node A Plus a table of primitives: Type: block, cylinder Dimensions: radius, length Transformation: 3x4 matrix + B C E * D Product of rotations, translations
Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 22 Point-in-solid test for CSG Test the point for inclusion in each primitive P Produces Boolean result (True/False) p Ignore for now on cases Evaluate Boolean expression Substitute P in the CSG expression by p Substitute Set theoretic operators by Boolean operators Union is OR, || Intersection is AND, && Difference is AND NOT, &&! Example: ((A+B)((CD)E)) yields ((a OR b) AND NOT ((c AND d) AND NOT e)) Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006
23 Details of point-in-CSG PinCSG(point p, node N) { if N.type in {+,*,-} then return (combine(N.operator, PinCSG(p,N.left), PinCSG(p,N.right))) else return PinP(p, N.type, N.dimensions, N.transformation) } - + Combine (op, left, right) { if op==+ then return (left OR right); if op==* then return (left AND right); if op==- then return (left AND NOT right);} A B PinP (p, type, Dim, xform) { C (x,y,z):=apply(p,inverse(xform)); If type=sphere then return(x2+y2+z2
If type=cylinder then return(x2+y2
pi Georgia Tech, IIC, GVU, 2006 25 Primitive(cylinder,radius,height) Expressed in their local coordinate system Defined by their intrinsic parameters Z Type = cylinder Dim[1] = radius Dim[2] = height Y How to test a point for inclusion in the cylinder? X Jarek Rossignac Point (x,y,z) lies inside if and only if (x2+y2
radius height inverse q = pre-image (p) Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC p Test q against the original primitive Georgia Tech, IIC, GVU, 2006 27 Issues How to convert from BSP to CSG ? How to convert from CSG to BSP ? Which is faster for Point-in-Solid tests Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 28
What you must remember Definitions of Boolean operators Definitions of linear half-spaces Point-in-half space tests for planes, spheres, cylinders What are BSP and CSG How to represent them How to perform point-in-solid tests on them How to come up with number of cells in line arrangement Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 29 A 2D example Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC
MAGIC Georgia Tech, IIC, GVU, 2006 30 A shape has many CSG reps Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 31 When is a primitive redundant A primitive A is redundant in S if S can be expressed using the other primitves, without A. Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 32 Is A redundant if A adds nothing to S?
Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 33 How to convert a CSG to its positive form? Apply de Morgan laws and push the complement down to the primitives Primitives complemented an odd number of times are negative (and hence unbounded) Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 34 What is the positive form of S?
S=(A+B)(CD)(EF) S = (A+B) (!CD) (!E+!F) A Jarek Rossignac B C E F D http://www.gvu.gatech.edu/~jarek A B !C MAGIC
MAGIC !E !F D Georgia Tech, IIC, GVU, 2006 35 Now assume CSG is in positive form Rename the negative primitives with new names so that they become positive (although infinite) primitives A CSG tree in positive form has only union and intersection operators Hence, in what follows we need not discuss what to do with difference operators We assume that the CSG tree has been converted into its positive form and that all primitives are positive (even though some may be unbounded) Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 36 What is the path of a primitive A? The parent and ancestors of A in the CSG tree.
Nodes in the path of A root A B C primitives Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC E F D Georgia Tech, IIC, GVU, 2006 37 How to compute the path? Path will be represented as a string of L or R symbols p=emptyString; path(root,p);
path(n,p) { if (n.isPrimitive) { n.myPath=p; else { path(n.left, p+L); path(n.right, p+R); }; }; Jarek Rossignac http://www.gvu.gatech.edu/~jarek L R LL LR LLL LLR A B C
MAGIC MAGIC LRL RL RR E F LRR D Georgia Tech, IIC, GVU, 2006 38 What are the branching nodes? Siblings of path nodes root A B C
E F Branching nodes of A D primitives Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 39 What are the path and branching nodes of D? Path nodes Branching nodes A Jarek Rossignac
B C E F D http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 40 What are i-nodes and u-nodes of A? i-nodes = branching nodes that are children of an intersection u-nodes = branching nodes that are children of a union Circle the i-nodes of A? Circle the u-nodes of A? A Jarek Rossignac http://www.gvu.gatech.edu/~jarek
B C MAGIC MAGIC E F D Georgia Tech, IIC, GVU, 2006 41 Practice i-nodes and u-nodes Circle the i-nodes of C? Circle the u-nodes of C? A Jarek Rossignac http://www.gvu.gatech.edu/~jarek
B C MAGIC MAGIC E F D Georgia Tech, IIC, GVU, 2006 42 What is the active zone of A in S? The active zone Z of primitive A in a given CSG expression of S is the region in which changes to A affect S. Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 43
How are I, U, and Z of A defined? I-zone: I = intersection of the i-nodes (or the universe w if none) U-zone: U = union of the u-nodes Active zone: Z = I U Compute I, U, and Z for A A I = EF B C E D F U = B+CD Z = EF (B+CD) = EF B (CD) Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC
Georgia Tech, IIC, GVU, 2006 44 Practice: Shade S and Z IDENTIFY S AND Z for primitive A Verify that changing A out of Z does not change S A B E F A C Jarek Rossignac D B C I = EF
E D F U = B+CD Z = EF (B+CD) = EF B (CD) http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 45 Point-in-solid test on CSG Classify(point P, node N) IF N is primitive, THEN RETURN(PMC(P,N)) ELSE RETURN(Combine(N.op, PMC(P,N.left),PMC(P,N.right))); A B E C Jarek Rossignac
F E F D A http://www.gvu.gatech.edu/~jarek MAGIC MAGIC B C D Georgia Tech, IIC, GVU, 2006 46 How to test whether a surfel is on? Surfel = point E on the boundary of a primitive A. Does it contribute to the boundary of S? Or can A be changed around E without affecting S? Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC
MAGIC Georgia Tech, IIC, GVU, 2006 47 Strategy for CSG rendering For each primitive A Generate a sufficiently dense set of surfels on the boundary of A For a cylinder, place surfels on a circle and slide the circle Classify surfels against Z Render those in Z Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 48 Blister: GPU-based rendering of Boolean combinations of free-form triangulated shapes John Hable & Jarek Rossignac College of Computing, IRIS cluster, GVU Center Georgia Tech, Atlanta, USA http://www.gvu.gatech.edu/~jarek/blister/ Jarek Rossignac
http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 49 CSG (Constructive Solid Geometry) Operators: A+B (Union) AB or A*B (Intersection) A !A (Complement) AB=A!B (Difference) B Primitives (solids): Bunnies, Triangle meshes Natural quadrics Subdivision shells Water-tight boundaries CSG expression: (A+B)(C (DE)) Define solids Parsing them yields a binary tree * +
A B C D Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 E 50 Examples of prior approaches 3-D: Voxels (classify wrt primitives, merge) [Meagher84, Breen89, Fang98, Chen00] 2-D: Trimmed faces (boundary evaluation) [Mantyla86, Hoffmann89, Krishnan97, Bierman01] 1-D: Rays from eye through pixels B A [Roth82, Ellis91, Pfister00]
0-D: Surface samples B A Model space (surfels) [Rossignac86, Bronsvoort87, Breen91] AB Image space (fragments) [Okino84, Sato85, Goldfeather86-89, Epstein89, Wiegant96, McReynolds96, Jansen95-87, Rossignac92, Stewart98, Fang00, Stewart02] Disjunctive form: 31,104 products Mixed Faces+fragments [Rappoport97] Jarek Rossignac http://www.gvu.gatech.edu/~jarek Samples+voxels [Adams03] MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 51 Blist form of a CSG tree Union A=1 i
A i A iA+i!AB=i(A+B) B i i!A!B=i!(A+B) Intersection A=0 i i A B i!A+iA!B=i!(AB) i Difference iA i i
A A i!A Jarek Rossignac http://www.gvu.gatech.edu/~jarek iAB iA!B=i(AB) !B i!A+iA!!B=i!(AB) MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 52 Blist of a symmetric difference Simple to support, but reduces the size of the worst case CSG models that we can handle. LR L !R R
ABC A Jarek Rossignac !B B http://www.gvu.gatech.edu/~jarek !C MAGIC MAGIC C Georgia Tech, IIC, GVU, 2006 53 Merging Blist sub-expressions L L L Jarek Rossignac R Union: L+R
R Intersection: LR !R Complement: !R !R http://www.gvu.gatech.edu/~jarek Difference: LR=L!R MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 54 Example of Blist * + A (A+B)*(C(DE)) B C
D i A B C D !E i A B C !D !!E E i((A+B)(C(DE))) i A B
C !D E i!((A+B)(C(DE))) Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 55 Use a positive CSG form (for simplicity) negative (complemented) primitive (A+B)(C(DE)) AB=A!B !(A+B)=!A!B !(AB)=!A+!B !!A=A (A+B)(C(!D+E)) * *
Conversion to positive form is a trivial recursion + A A B C B + C D Jarek Rossignac * + !D E http://www.gvu.gatech.edu/~jarek
MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 E 56 Algorithm for computing Blist labels Assigns to each link the label (color) of its final destination primitive C i C A P.n=A P.t=C P.f=B B B Jarek Rossignac t=D f=false f Going right: inherit t and f. Going left: pick up blue value t=true
f=false f=C E char lml (int m) { # left most leaf of right child char leftMost; if((o[m]!='*')&&(o[m]!='+')) {leftMost=o[m];} else {if (o[m]=='+') {f[m]=lml(r[m]); } else {t[m]=lml(r[m]); }; leftMost=lml(l[m]); }; return(leftMost); } t=true f=false t=D E With each primitive P, store its name, P.n and its P.t (upper) and P.f (lower) labels t=true t=true f=B t !D f f=false f=B
t=D f=C C f Assume positive form t !D void mb (int m, char pt, char pf) { if((o[m]!='*')&&(o[m]!='+')) { blistName[pc]=o[m]; blistIfTrue[pc]=pt; blistIfFalse[pc]=pf; t[m]=pt; f[m]=pf; pc++;} else {if (o[m]=='+') {mb(l[m],pt,f[m]); } else {mb(l[m],t[m],pf); }; mb(r[m],pt,pf); }; } http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 57 Point-in-CSG classification using Blist C
i A C B B C f t !D !D t E E f f Workspace: Boolean parity; 6-bit integer next; For each primitive P in Blist do: parity := true if point is in-or-on P; If (next==P.n) {if (parity) {next=P.t} else {next=P.f}}; The final content of next indicates whether the CSG expression is true or false Jarek Rossignac
http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 58 We can only afford 6-bit labels C i C A B B Assign integers as needed. 1 i A C !D A E
f 1 3 4 4 C :1 !D:3 2 Jarek Rossignac C :1 B:0 0 E f 2 Reuse labels of primitives that have already been reached. 1 1 1 i
t f B:0 0 t !D 0 http://www.gvu.gatech.edu/~jarek E:5 5 2 1 1 !D:1 E:2 2 0 0 Need 3 labels
MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 59 Minimizing the number of labels Original: (A+((B+((C+((D+E)+F))+G))+H))+(I+(J+(K+L)M)N): 5 labels Can swap left and right arguments. Strategy: swap to make tree left-heavy A+B B+A, AB BA Cost swaps: labels Height(K+L)+JM+IN+(A+(H+(B+(G+(C+(F+(D+E))))))) swaps: D+E+F+C+G+B+H+A+(((K+L)M+J)N+I): :3 4 labels There are 64 6-bit labels. We prove that no CSG tree with < 3909 primitives requires more than 64 labels Recently developed linear optimization: No CSG trees with < 263 primitives requires more than 64 labels. Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC
Georgia Tech, IIC, GVU, 2006 60 Improving Blist worst-case footprint Height-based pivoting (described in the paper) could guarantee only 3909 primitives New cost-based pivoting with 6 stencil bits guarantees support for all CSG trees with less than 263 primitives! In general b stencil-bits support n=2b labels and n labels suffice for all Blist expressions with up to p=2n11 primitives Smallest expression requiring 5 labels has 15 primitives: ((AB+C)(DE+F)+G)((HI+J)(KL+M)+N)+O Original (5 labels): (A+((B+((C+((D+E)+F))+G))+H))+(I+(J+(K+L)M)N) Height swaps (4 labels): D+E+F+C+G+B+H+A+(((K+L)M+J)N+I) Cost swaps (3 labels): (K+L)+JM+IN+(A+(H+(B+(G+(C+(F+(D+E))))))) Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 61 Blist is a very special decision graph Boolean functions: many representations [Moret82] Binary Decision Graphs (BDG) [Akers78] Reduced Function Graphs (RFG) [Bryant86] Acyclic BDGs without repetition
Constructed through Shanons Expansion [Shannon38] Removing empty leaves yields BSP trees Reduction: recursively tests graph isomorphisms # nodes may be exponential in # primitives Size depends on order [Payne77] (optimal is NPhard) Footprint is log2N bits Blist [Rossignac99] RFG of a Boolean expression with +, *, operators Linear construction & optimization cost # nodes = # primitives = N Footprint may be compressed to log2log2N bits (A+B)CD=(A+B)(!C+!D) !A(B(!C+!D)+A(!C+!D) !A(!B+B(!C+!D)+A(!C+!D) !A(!B+B(C!D+!C)+A(C!D+!C) A B !C !C !D !D A B !C !D Jarek Rossignac
http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 62 Blister Overview Repeat until all pixels are locked Peel: Push the unlocked fragments to the next layer Scan each primitive: compute foremost fragment behind current layer Lock: Identify and lock fragments on the CSG solid For each primitive P: Classify active fragments by toggling parity bit For all active pixels: Update the Blist next value Contributions of layers (front-to-back) Several primitives may contribute to a layer Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 63
Peel strategy UNC: Peel each primitive with a counter [Goldfeather-Hultquist-Fuchs SIG89] 5 4 1 2 3 6 IBM+: Peel a product with a Depth-Interval Buffer? F=previous layer, B=infinity If (F
MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 64 Peel example Peel the arrangements of all primitives taken together For each layer, scan the front/back faces of positive/negative primitives Use a Depth-Interval Buffer to advance the layer [Epstein-Jansen-Rossignac89] Produces layers of fragments in front-to-back order (A+B)C A Negative primitive (A+B)C! Third layer fragments B C Second layer fragments First layer fragments Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006
65 Peeling: Implementation details Initialization: Compute (small) set of primitives that cover the CSG solid AB A, A+BA+B, AB smaller of A and B Store front F and back B of the covering set in texture memory Render with GL-LT and GL-GT For each layer: F contains previous layer depth B is initialized to infinity Render primitives In the pixel-shader (z=depth of fragment) If ( z
Pixels with fragments on the CSG solid S are locked The next layer is only computed at the active (unlocked) pixels (A+B)C A B C Third layer locked Second layer locked First layer locked Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 67 Fragment/primitive classification We want to classify the fragments of each active pixel q in the current layer whose depth is S[q] Scan P generating fragments (pixel q, depth z) If ((q is active) && (z
Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 68 Classifying fragments on P Prior art tested ghost fragment moved back by e: c If ((q is active) && (z
MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 69 ON/ON cases A B C (AB)+C Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 70 Cant remember past classifications? Only 6 stencil-bits per pixel to keep past classification results Storing Boolean for each primitive: < 7 primitives Storing a stack of partially evaluated results < 65 primitives Using a disjunctive form of CSG tree: no limit on N Goldfeather86-89, Epstein89, Wiegant96, Rossignac92, Stewart98, Stewart02 But the number of products can grow exponentially! *
* * * * + * + + * * + CSG expression has 48 primitives. Disjunctive form has 31,104 products with 5 primitives per product * + * + + *
* + + * + + * + + * + + + (No pruning possible) So use Blist instead! Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006
71 Lock for layer 2 in the example Fragments at all active pixels are classified in parallel against each primitive. Their stencils are updated (based on the classification and their previous value). After the last primitive, fragments on the CSG solid are locked, others stay active. (A+B)C A Active fragments of layer 2 Scan A Out of A (for B) B C In-or-on A (for C) Scan B In-or-on B (for C) Scan C In-or-on C! (locked) Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Out of C (active) Georgia Tech, IIC, GVU, 2006 72
Use Blist to merge past classifications 1 i A 1 1 C :1 B:0 0 1 0 !D:1 1 E:2 2 0 0 Initialization: P.t
Rearrange the CSG tree to minimize the number of labels With each primitive, P, associate its 3 Blist labels: P.n, P.t, P.f P:n P.f In the stencil of each pixel store: parity (bit-0), next (bits 1-6) To classify and lock the fragments of the current layer For each primitive P in Blist do: Scan P {toggling parity when P is in front of the tested fragment} Scan all active pixels {If (next==P.n) {if (parity) {next=P.t} else {next=P.f}}} Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 73 Updating the stencil bits of next // Stencil=(parity-bit,next) // if (parity-bit==1 and next==P.n) then next:= P.t IF (Stencil==10000010) {Stencil:= 10000011;} // if (parity-bit==0 and next==P.n) then next:= P.f IF (Stencil==00000010) {Stencil:= 00000000;} A 0000010 B ...
0000000 C 0000011 Speed-up suggested by Mark Kilgard (nVidia): Mask=next XOR P.t; Then toggle next where it agrees with Mask glStencilMask( P.t ~ next ); glStencilFunc( GL_EQUAL, P.t | 0x80, 0xff ); glStencilOp( GL_KEEP, GL_KEEP, GL_INVERT ); Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 74 An example Layer 1 Layer 2 Layer 3 Layer 4 Free fragments On fragments Locked
fragments Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 75 Timing results nVidia GeForce 6800 Bunny has 574K triangles, Bunny2 has 2.3M Average over random directions Actual layers processed when we prune active pixels prims layers kf T (sec) Widget 4 4.00
3.85 0.018 Bunny 4 9.13 6.81 0.325 Bunny2 4 9.09 6.77 1.200 Complex 20 14.1 9.17 0.093
Gear 48 36.4 25.6 0.460 Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 76 Extensions Transparency (not always correct) Internal faces increase opacity Shadows (shadow buffer) Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006
77 Ongoing & future work Increase complexity for which Blister is guaranteed to work Increased from 3909 to 263 primitives when using 6 stencil bits Improve performance Preliminary Results: already 20% faster Select correct color for fragments on 2 primitives Use Active Zones [Rossignac&Voelcker 89] Correct surface transparency Custom classification Voxelization / volumetric rendering Interpolate / integrate between layers Parallelization (SLI/Crossfire) AFR (Alternate Frame Rendering between two graphics cards) Split Screen/Tiles, but shared texture Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 78
Summary of Blister Can render all CSG trees with up to 263 primitives Simple, efficient CSG-to-Blist conversion Time complexity: O(DepthComp*Primitives) Efficient implementation on GPU Typical performance: 2 fps for CSG of 50 primitives Can be used for shadows (and transparency) Many improvements/extensions underway * 1 1 + A B i A C: 1 B:0 0 C
0 D Jarek Rossignac 1 1 1 D!: 1 E:2 2 0 0 E http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 79 Constructive Solid Trimming (CST)
Extension of CSG Use CSG expression for trimming surfaces GPU support for realtime rendering Use Active Zone Z of A as the CST for primitive A Advantages: Faster No ghost pixels Internal structure Correct transparency Contacts / interferences Cut-outs / painting Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 80
No ghost pixels Classifying surfels against active zones eliminates ghost pixels Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 81 Reveal internal structure Make selected faces completely transparent reveal internal structure Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 82 Correct transparency Produce correct images of semitransparent CSG models Jarek Rossignac
http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 83 Contacts / interferences Highlight contacts and interferences for assembly design Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 84 Cut-outs / painting Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 85
Assigned Reading Two papers: Active Zones in CSG for Accelerating Boundary Evaluation, Redundancy Elimination, Interference Detection and Shading Algorithms Jarek Rossignac and Herbert Voelcker ACM Transactions on Graphics, Vol. 8, pp. 51-87, 1989. Blister: GPU-based rendering of Boolean combinations of free-form triangulated shapes John Hable and Jarek Rossignac ACM Transactions on Graphics, SIGGRAPH 2005. Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 86
Computing Fundamentals Chapter 3: Input, Output, and Storage
Define output and explain the types of output devices available. Differentiate between types of monitors and explain their features. ... Plotter: A large-format printer that creates high precision documents such as maps and engineering drawings.