Volume Visualisation - Swansea

BCTCS 2006 The Theory of Spatial Data Types and Constructive Volume Geometry Constructive Volume Geometry Is an algebraic framework for the high-level Specification, Representation, Manipulation, and Rendering of spatial data types. We use CVG to build complex scenes using algebraic operations on fully 3D spatial objects. CT planet, Min Chen, 1999

M. Chen and J. V. Tucker, Constructive volume geometry, Computer Graphics Forum, Vol.19, No.4, 281-293, 2000. CVG Spatial Objects A spatial object is a tuple o = (O, A1, A2, , Ak) of scalar fields defined in R3, including an opacity field O: R3 [0,1] and possibly other attribute fields: A1, A2, , Ak: R3 R, k 0. Visibility of every point in R3 specified by opacity attribute where 0 is transparent and 1 is opaque. O: sphere R: noise G: constant

B: constant CVG Scene with Several Objects scene object field object ...... object O R G B Ge Ka Kd Ks N Dn Rfl Rfr Txt ... Constant Built-in mathematical scalar field

Volume Dataset Procedural scalar field Colour-separated image plus various mappings CVG Operations: 4 Colour Channel Model (I) o1=(O1, R1, G1, B1) o2=(O2, R2, G2, B2) (o1, o2) CVG Operations: 4 Colour Channel Model (II) (o1, o2)

(o1, o2) (o1, o2) (o2, o1) CVG Operations: 4 Colour Channel Model (III) operations on spatial objects operations on scalar fields operations on scalars (o1, o2) = ( Max(O1, O2), Select(O1, R1, O2, R2), Select(O1, G1, O2, G2),

Select(O1, B1, O2, B2) ) Max(O1,O2)(x) = max(o1(x),o2(x)) Select(S1,T1,S2,T2)(x) = select(s1(x),t1(x),s2(x),t2(x)) max(s1, s2) = select(s1, t1, s2, t2) = { s1 s2 s1 s2 s1 < s2 { t1

t2 s1 s2 s1 < s2 Algebraic Specification and CVG Equational axioms on scalars extend to axioms on spatial objects. Example: Associativity law for the CVG operation: (o1, (o2,o3)) = (

(o1,o2),o3) defined using Max, Select Associativity of Max, Select on scalar fields pointwise-lifting of operations Associativity of max, select on scalars Hierarchical Data Representation composite volume object (o1, o2) o1 o2 convex

volume object convex volume object 1 CVG Tree (I)

CVG Syntax and Semantics CVG Term:

Define algebraic terms and CVG term evaluation (= structural induction) in the usual way. Expressiveness of CVG CVG is an algebraic framework for volume graphics. Question: Do the CVG terms define all the spatial objects one wants? We can show the answer is: Yes 1. Any continuous spatial object can be approximated by a CVG term to arbitrary accuracy. 2. Given any computable spatial object o and an > 0 one can compute a CVG term to which approximates o to within the error margin .

In fact we prove this by a general theory of spatial objects General Theory of Spatial Data Types: I Algebra The -operations on A are pointwise lifted to F(X,A): FF(X,A)(1,, n)(x) = fA(1(x),, n(x)) which preserves the equivalence of term evaluation: [t]F = [t]A Validity Theorem: For any equation t = t the following are equivalent: 1. t = t is valid in A, 2. t = t is valid in F(X,A), Corollary: If A satisfies a set E of equations then F(X,A) satisfies E. Examples: Axioms for commutative rings, Axioms for CVG.

General Theory of Spatial Data Types: II Topology We use topology to define the notion of approximation. C(X,A) = the set of all continuous total spatial data types from X to A X is any topological space and A is a topological -algebra. C(X,A) has the compact-open topology: Basic open sets are

U W(J,U) = {f | f[J] U}, J compact subset of X and U open in A. For X compact and A = R, the compact-open topology on C(X,R) is equivalent to the topology defined by the sup norm: || f g || = sup{z in X}|f(z) g(z)| with open sets: B(f, ) = {g in C(X,R) : || f g || < } R We want a nice function g such that g<

+ g - K compact Dense Subsets of C(X,R) We say that a set D is dense in C(X,R) if for any W(J,U) we have D U W(J,U) 0.

For K compact, there is a spatial object g in D arbitrarily close to any given in C(K,R): || g || < . If D is dense on C(X,R) then spatial objects in D can approximate all continuous spatial objects. We use the Stone-Weierstrass Theorem when we deal with approximation on a compact K, but what about non-compact X? Completeness of Spatial Data Types

Is it possible to find a collection of spatial operators on C(X,R) = {F1,,Fk} and a subset B of C(X,R) consisting of continuous basic spatial objects b1, bn such that every continuous spatial object in C(X,R) can be approximated by an object t(b1, bn) from the subalgebra generated by the operations on B? Basic Spatial Objects and Primitive Operations Basic spatial objects in B should have the properties: 1. separate the points of space X 2. contain a non-zero spatial object Operations we need in sw

1. 2. 3. Addition Multiplication Scalar Multiplication Approximation Theorem for Spatial Objects Theorem: Let C(X,R) be the set of all continuous total spatial objects, and B is a subset with Properties 1 and 2. Using only the operations in sw the subalgebra sw generated by the repeated application of operations in sw on B can approximate all spatial objects in C(X,R). Proof Idea: Localize the problem to a compact space K, find an approximate, and then show it works on C(X,R) Pick any W(K,U) in C(X,R). We want a term t in sw such that [t]C(X,R)(b1,bn) is in W(K,U).

Inverse Limit Construction Theorem: LimI in ZC(I,R) C(X,R) Homeomorphism: (f) = (,fK,,fJ,fI,) Sequences of restrictions directed under set inclusion by the family Z of all compact sets of X. Shows that the compact-open topology behaves the same way on both sets.

Each coordinate (f)(K) is the restriction fK in C(K,R). Proof Sketch: Restriction Homomorphism C(X,R) LimI in ZC(I,R) K K C(K,R) The mapping K = K is a homomorphism and restricts C(X,R) to C(K,R)

The set K(B) of basic spatial objects restricted to a compact K satisfies Properties 1 and 2 on the coordinate space C(K,R). Proof Sketch: Approximation on C(K,R) We can approximate on a compact K, so by Stone-Weierstrass sw is dense in C(K,R). Meaning that there is a term t in sw such that [t]C(K,R)(K(b1),, K(bn)) is in W(K,U). Since K is a homomorphism: [t]C(K,R)(K(b1),, K(bn)) = K([t]C(X,R)(b1,,bn))

i.e. the term t in SW evaluates to the same points in C(X,R) and so [t]C(X,R) is in W(K,U). Goals Extensions of the Stone-Weierstrass and spatial object approximating theorems Computability and effectivity issues; While programs over C(X,A) Graphics applications: Discretisation D : C(R3,A) C(Z3,A) Rendering R: C(R3,A) C(Z2,A)

Recently Viewed Presentations

  • Welcome to the RedRover Responders Webinar Volunteer orientation

    Welcome to the RedRover Responders Webinar Volunteer orientation

    A dog owner leaves the dog in a car, thinking that going into the store will only take 5 minutes. But first they run into an old friend, then the item they came for is out of stock, then the...
  • Thesis - ECLAP

    Thesis - ECLAP

    Thesis Formula. A specific subject + a specific condition, feeling, or stand = an effective thesis statement. Video games are an important developmental tool for young people because they enhance eye-hand coordination, develop complex problem-solving skills, and promote self-confidence.
  • ACT: Strategies &amp; A

    ACT: Strategies & A

    Information on specific content knowledge affords teachers the ability to identify and address gaps in understanding that may limit student success in STEM-related occupational fields. Social Studies. Three parts for U.S. History. Grade-specific social studies content knowledge and analytical skills
  • Approximately 72% of the planet's surface is covered

    Approximately 72% of the planet's surface is covered

    The chemosynthetic vent bacteria are the base of the food chain at hydrothermal vents. Vent bacteria are capable of producing 'cell food' by chemosynthesizing the minerals (especially sulfur compounds) in the water.
  • United States Supreme Court Criminal Law Decisions of the ...

    United States Supreme Court Criminal Law Decisions of the ...

    Elonis says his Facebook posts were simply rap lyrics. At trial, Elonis argued that the First Amendment requires the government to prove he intended to make a "true threat," because the "essence of crime is wrongful intent."
  • mssusanha.weebly.com


    ELA: Connotation. Nestled away in the corner of his tidy bedroom, the walls covered baseball wallpaper, baseball pennants, and baseballs signed by his favorite players, Ed sat hunched over a large piece of poster board he was keeping mysteriously hidden...
  • PANCREAS AND GLUCOSE By Juliana Xie Pan-creas! Greek:

    PANCREAS AND GLUCOSE By Juliana Xie Pan-creas! Greek:

    Diabetes: In the United States, 25.8 million adults and children (8.3% of population) have diabetes. Systemic disease. Pancreatic cancer - 4th most common cause of cancer-related death, extremely poor prognosis. Pancreatitis is an emergency situation
  • Presentación de PowerPoint

    Presentación de PowerPoint

    ANALISIS SMED Preparación p/SMED Fase 1: Separación I y E Fase 2: Conversión I a E Fase 3: Refinamiento Etapa 1 y 2: Actividades del Operador Cambio de herramentales Extrusor Primario Equipo Actividad que agrega valor No agregan valor NV-1...