\documentclass[a4paper, 11pt]{article}

\usepackage[latin1]{inputenc}
\usepackage{amssymb , amsmath}
\usepackage{graphicx}
\usepackage{subfigure}

\title{CG2 SS2011, Eduard Gröller}
\author{Onur Dogangönül}

\begin{document}

\maketitle

\tableofcontents

\section{Graphical Programming}
	\subsection{Introduction}
		\begin{itemize}
		\item Process graphical objects and data.
		\item Early standards:
			\begin{itemize}
			\item GKS (Graphical Kernel System, 1977)
				\begin{itemize}
				\item 1st low-level ISO standard
				\item Provides a set of drawing features for 2-dim vector graphics
				\end{itemize}
		\item PHIGS
			\begin{itemize}
			\item Programmer's Hierarchical Interactive Graphics System (ISO/IEC 9592)
			\item Defines a scenegraph-API
			\end{itemize}
		\item Both standards declined with the rise of OpenGL.
		\end{itemize}
		\item X Window System
			\begin{itemize}
			\item Software/network protocol provides basis for GUI for networked computers
			\item HAL (hardware abstraction layer): software is written using generalized set of commands
			\item Device independence/reuse of programs on computers that implement X
			\end{itemize} 
		\item OSF/Motif: GUI specification/widget toolkit for building applications that follow X Window System
		\item Open Inventor: 
			\begin{itemize}
			\item High level 3D graphics API
			\item Scene graph oriented
			\item E.g. engines, sensors, manipulators
			\end{itemize}
		\item VRML
			\begin{itemize}
			\item Virtual Reality Modeling Language
			\item Std file format for representing 3dim interactive vector graphics
			\end{itemize}
		\item X3D
			\begin{itemize}
			\item ISO standard XML-based file format representing 3D computer graphics
			\item Successor of VRML
			\end{itemize}
		\item OpenGL . 
			\begin{itemize}
			\item HW independent interface to graphics hw
			\item No rendering context or user input management 
			\item Interface between OS and OpenGL (GLFW etc..)
			\end{itemize}
		\end{itemize}

	\subsection{Java3D}
		\begin{itemize}
		\item Builds upon OpenGL/DirectX layer
		\item Scenegraph API
			\begin{itemize}
			\item Viewing subtree: definition and parameters for rendering and projection.
			\item Content subtree: defines the scene (geometry and transformations).
			\end{itemize}
		\item Renderer
			\begin{itemize}
			\item Double buffering (RGBA)
			\item Infinitely traversing SG
			\item Takes care of transparency
			\item Influence of fog, lights, sound
			\item Optimized for rendering
			\end{itemize}
		\item Node States (Capabilities):
			\begin{itemize}
			\item Detached: After creation, all ops legal
			\item Live
				\begin{itemize}
				\item Node in SG
				\item Set permission via setCapability(..)
				\end{itemize}
			\item Compiled: Optimized by renderer (mods restricted)
			\end{itemize}
		\item Node Types
			\begin{itemize}
			\item Group nodes
				\begin{itemize}
				\item BranchGroup: grouping of shapes (only detachable/relocable node)
				\item TransformGroup: t applied to all children
				\end{itemize}
			\item Shape3D
				\begin{itemize}
				\item Defines object within scene
				\item Geometry: polygon related info
				\item Attributes: material definition, rendering mode, ...
				\end{itemize}
			\item Geometry nodes: coords, normals, RGB(A) color, tex coords, indices (for indexed types) ...
			\end{itemize}
		\item Helper Classes
			\begin{itemize}
			\item com.sun.j3d.utils.*
				\begin{itemize}
				\item SimpleUniverse: fast viewing model setup
				\item Mouse transform mapping for interactions
				\item Simple geometrical Objects: cube, ...
				\end{itemize}
			\item javax.vecmath.*: Tuple, Point, Vector, Matrix, Quaternions with their ops
			\item javax.media.j3d.Transform3D: Orth/Persp. projection, scale, rotate, transalte, ...
			\end{itemize}
		\item Appearance: defines attributes for rendering
			\begin{itemize}
			\item Polygon mode (points, wireframe, fill)
			\item Culling
			\item Rendering attrib: Depth buffer, alpha blending
			\item Transp/Color if not per vertex
			\item Material (reflex coeffs) and texture images
			\end{itemize}
		\item Lighting:
			\begin{itemize}
			\item Require bounds delimit area of infl
			\item Ambient, Direcitonal (inf dist), pointlight
			\end{itemize}
		\item Behaviors 
			\begin{itemize}
			\item Events for SG
			\item Actions executed if criteria met: time trigger, kbd/mouse event, object picking, collision, frames elapsed, ...
			\item Boolean comb of criteria
			\item Area of relevance
			\item Influence transformation, geometry, ...
			\end{itemize}
		\item Viewing model
			\begin{itemize}
			\item Supports multiple Canvas3D objects (stereo rendering, cave).
			\item Supports tracking
			\item Detailed description of viewer's eyes/ears
			\end{itemize}
		\end{itemize}

\section{Advanced Modelling}
	\subsection{Motivation}
		\begin{itemize}
		\item Real world phenomena comprise: complex geometry, large defs, topological changes, fuzzy objs bounds 
		\item Hard to model with meshes: E.g. Smoke, fire, fluids, fur, hair, grasss
		\end{itemize}

	\subsection{Particle Systems}
		\begin{itemize}
		\item Modelling of objs changing over time
		\item Rain, snow, clounds, smoke, fire, waterfalls, water spray, grass,...
		\item Render certain num of particles
		\item Changing particle params: Loc, speed, appearance
		\item Die after a time
		\item Particle shapes: spheres, boxes or arb models
		\item Rnd processes gen objs within defined region
		\item Shapes may be small spheres, ellipsoids, boxes, ...
		\item Size, color, transparency, movement can vary randomly.
		\end{itemize}

	\subsection{Implicit Modelling}
		\begin{itemize}
		\item No fixed shape/topology
		\item Molecular structs, water droplets, metling objs, muscle shapes
		\item Shape/Topology change in motion/proximity to other objs
		\item No seams, oriented surface (in/outside def), differentiable, closed, continuous
		\item Imp eq doesn't express a var in terms of another var
		\item Surface of imp model is set of points fullfilling given imp eq
		\item Also called level curves, iso contours or contour lines.
		\end{itemize}

		\subsubsection{Blobby Objects}
			\begin{itemize}
			\item Modelling as distri functions over region of space
			\item E.g. comb of gaussian density funcs
				\begin{itemize}
				\item $f(x,y,z) = be^{-ar^2}$
				\item r ... distance to center point $$r = \sqrt{(x-x_0)^2 + (y-y_0)^2 + (z-z_0)^2}$$
				\item k gaussian bumps at k control points $(x_k, y_k, z_k)$ are comb $$f(x,y,z) = \sum_k b_k e^{-a_k - r^2_k}-T=0$$
				\item $r^2_k = (x-x_k)^2 + (y-y_k)^2 + (z-z_k)^2$
				\item Param T as threshold, params $a_k, b_k$ adjust shape of ind blobs
				\item Neg $a_k, b_k$ model dents
				\end{itemize}
			\item Metaball model/Soft-object model use density functions that fall of to 0 in finite interval
			\end{itemize}

		\subsubsection{Superquadrics}
			\begin{itemize}
			\item Quadrics: cruve in plane, plane in 3d space or hyperplane in nd space etc (given by quadratic func)
			\item Generalization of quadric reps (Add params to quadric eq)
			\item Num of add params equal to dimension of obj
			\item Increased flex for obj shapes
			\item Superellipse
				\begin{itemize}
				\item Imp eq: $f(x,y) = \left(\frac{x}{r_x}\right)^{\frac{2}{s}} + \left(\frac{y}{r_y}\right)^{\frac{2}{s}} = 1$
				\item $r_x, r_y$ params of ellipse, s param of superellipse (e.g. s = 1, normal ellispe)
				\item Also parametric eq for superellipse in reader
				\end{itemize}
			\item Superellipsoid
				\begin{itemize}
				\item Imp eq: $f(x,y,z) = \left[ \left(\frac{x}{r_x}\right)^\frac{2}{s_2} + \left(\frac{y}{r_y}\right)^{\frac{2}{s_2}} \right]^\frac{s_2}{s_1} = 1$
				\item E.g. normal ellipsoid for s = 1 
				\item Parametric for superellipsoid in reader
				\item Superquadric shapes comb for more complex structs
				\end{itemize}
			\end{itemize}

	\subsection{Procedural Modeling}
		\begin{itemize}
		\item Complex geometry build with set of production rules
		\item Simple primitive and repetitive structs
		\item Often params that change the appearence.
		\item Sweeps 
			\begin{itemize}
			\item For trans, rot or other symmetries
			\item Spec two dim shape (circle, rect, spline-curves, ...), and curve to move along
			\item Pros/Cons
				\begin{itemize}
				\item Generates complex shapes
				\item Hard to render
				\item Difficult modelling
				\end{itemize}
			\end{itemize}
		\end{itemize}

	\subsection{Structure Deforming Transformations}
		\begin{itemize}
		\item Used in comb with other modeling tech
		\item Tapering: non-linear scaling, where scaling factors are functions (see matrix in reader)
		\item Twisting: non-linear rot, where rot params depend on coords of input point
		\item Bending: non-linear rot, where rot params depend on coords of input point
		\end{itemize}

	\subsection{Other}
		\begin{itemize}
		\item Cellular Texture Generation
			\begin{itemize}
			\item Cellular particle system with cell state, programs and extracellular environments
			\item Cell: grp of polygons ith texture and transparency maps
			\item Cell state: pos, orient, shape, chemical concentrations (reaction-diffusion), ...
			\item Cell programs: go to surface, die if too far away, align, adhere to other cells, divide until surface covered
			\item Extra cellular env: neighbor orientiation, concentration, ...
			\item E.g. fur - cells similarly oriented like neighbors
			\end{itemize}
		\item Visualization of Knitwear
			\begin{itemize}
			\item Sim of 3d struct with instanced volume elements
			\item 2d cross section swept along parametric curve
			\item Rendering with raycasting (curved rays)
			\end{itemize}
		\item Fractal Terrain Sim
		\item Plant Rendering Population spec: Explicit spec (survey, interactive) or procedural gen 
		\end{itemize}

\section{Advanced Modelling 2}
	\subsection{Parametric Curves/Surfaces Overview}
		\begin{itemize}
		\item Param curves
			\begin{itemize}
			\item $c:c(u) = \begin{pmatrix} x(u) \\ y(u) \\ z(u) \end{pmatrix}$ , $u \in [a,b] \subset \mathbb{R}$
			\item $x(u), y(u), z(u)$ are diff functions in u
			\item Tangent vec: $t(u) = \frac{d}{du} c(u)$
			\item c regular in $c(u_0) \iff t(u_0) \neq 0$
			\item c regular $\iff$ c can be param that all curve points are regular
			\end{itemize}
		\item Param surfaces
			\begin{itemize}
			\item $s:s(u,v) = \begin{pmatrix} x(u,v) \\ y(u,v) \\ z(u,v) \end{pmatrix}$ , $(u,v) \in [a,b]\times [c,d] \subset \mathbb{R}^2$
			\item x,y,z are diff in u and v
			\item Tangent plane: $t_0(l,m) = s(u_0,v_0) + ls_u(u_0,v_0) + ms_v(u_0,v_0)$
			\item Normal vec: $n(u_0, v_0) = s_u(u_0,v_0) \times s_v(u_0,v_0)$
			\item s regular in $s(u_0, v_0) \iff n(u_0,v_0) \neq 0$
			\item s regular $\iff$ s can be param so that surface points regular
			\end{itemize}
		\end{itemize}

	\subsection{Curves}
		\subsubsection{Bezier Curves}
			\begin{itemize}
			\item Given n + 1 points $b_0, ..., b_n \in \mathbb{E}^3$ and arb $t \in \mathbb{R}$
			\item Set $b^r_i := (1-t)b^{r-1}_i + tb^{r-1}_{i+1}$ with $b^0_i := b_i$
			\item $b_0^n$ is a curve point
			\item Points $b^{n-1}_0$ and$ b^{n-1}_1$ determine tangent line in $b^n_n$
			\item Exp parametric rep: $b(t) = \sum^n_{i=1} b_i B^n_i(t)$, $B^n_i(t$ are Bernstein polynoms of nth deg
			\item Properties
				\begin{itemize}
				\item Affine invariance: affine transform of control points is affine trans of curve
				\item Convex hull: curve lies inside convex hull of control points
				\item Enpoint interpolation: first/last control points lie on curve
				\item Linear precision: all control points lie on line, bezier curve is a line
				\item Variantion diminishing: curve has no more intersection with plane than its bezier polygon
				\end{itemize}
			\item Disadvantes
				\begin{itemize}
				\item Changin one control points changes whole curve
				\item Degree of curve depends on number of control points: Higher flexibility - more control points
				\end{itemize}
			\item Important algorithms
				\begin{itemize}
				\item Degree eval: Add new control points for higher degree without changing shape
				\item Subdivision: Increase flex without increasing complexity
				\end{itemize}
			\item Evaluation: horner sheme like forms for faster eval
			\end{itemize}

		\subsubsection{B-Spline Curves}
			\begin{itemize}
			\item Piecewise polynomial curves of k-1 degree
			\item Degree almost ind from num control points
			\item Allow local control
			\item Given n+1 control points (boor points) and knot vector $U=(u_0, ..., u_{n+k})$
			\item B-spline curve s(u) is piecewise poly curve of order k (degree k-1) with $ 1 \leq k \leq n + 1$ of form $$s(u) = \sum^n_{i=0} d_i N^k_i(u)$$
			\item N ... normalized b-spline basis funcs (recursive def)
			\item Properties
				\begin{itemize}
				\item Affine inv
				\item Convex hull
				\item Variation diminishing
				\item Local support: changes only in local segments etc..
				\end{itemize}
			\item Special types
				\begin{itemize}
				\item Form of knot vector determines special cases 
				\item Open 
				\item Closed: Kontrol points closed path
				\item Uniform: Spacing between knot values constant (uniform B-spline), fitts better for algorithms due to periodic basis funcs
				\end{itemize}
			\item Evaluating B-Spline Curves (de Boor algorithm)
				\begin{itemize}
				\item Generalized de Casteljau, same principle of linear interpolation
				\item To evaluate s(u) do recursion (see reader)
				\item Direct evaluation (alternative)
					\begin{itemize}
					\item Find knot span in which parameter value lies
					\item Compute non zero basis func
					\item Mult value of basis func with corresp control point
					\end{itemize}
				\end{itemize}
			\item Knot insertion/Knot refinement
				\begin{itemize}
				\item Knot insertion does not change shape, but refines segmetation
				\item Increase flexi of curve, compute derivs, split curves or eval curve
				\item de Boor alg also knot insertion alg
				\item Algs with simultaneously knot insertion (knot refinement)
				\end{itemize}
			\end{itemize}

		\subsubsection{Rational Curves}
			\begin{itemize}
			\item Conic sections and quadrics have rational parametrization
			\item $c(u) = \frac{1}{w(u)}\begin{pmatrix} x(u) \\ y(u) \\ z(u) \end{pmatrix}$,$u \in I \subset \mathbb{R}$
			\item More elegant useful rep using homogeneous coords in $\mathbb{E}^4$
			\item Original curve interpreted as projection of curve on hyperplane $w(u) = 1$ in $\mathbb{E}^4$
			\item Rational Bezier Curves
				\begin{itemize}
				\item $b(u) = \frac{\sum^n_{i=0} w_ib_iB^n_i(u)}{\sum^n_i=0w_iB^n_i(u)}$
				\item If $w_i = 1$  same as polynomial bezier curve
				\item Properties
					\begin{itemize}
					\item Same properties as non rational
					\item Projective invariant
					\item Does not lie inside control poly if weights neg
					\item Weights as additional design param
					\end{itemize}
				\item Same algs can be applied for rational curves with homogeneous rep
				\end{itemize}
			\item Non Uniform Rational B-Spline Curves (NURBS)
				\begin{itemize}
				\item Most imp and flexi design elements provided in CAD systems
				\item Polynomial/Rational Bezier and B-spline curves are subsets of NURBS
				\item Properties same as rational bezier curves
				\item Chaning weights affects only segment
				\end{itemize}
			\end{itemize}
	
	\subsection{Surfaces}
		\begin{itemize}
		\item Tensor product surfaces
			\begin{itemize}
			\item Surface as moving curve that changes
			\item Changing curve means changing control points
			\item Leads to tensor product surface
			\end{itemize}
		\item Bezier surfaces
			\begin{itemize}
			\item Tensor product bezier surfaces analog properties to bezier curves
			\item Apply algorithm on curves
			\end{itemize}
		\item B-spline surfaces: Analog properties, again all algs apply
		\item Bezier Triangles: see reader
		\item Subdivision Surfaces
			\begin{itemize}
			\item Generated from base mesh, iteratively smoothing
			\item Mesh converges to a limit surface through iterations
			\item Charles Loop subdivision
				\begin{itemize}
				\item For triangle meshes only
				\item Split each triangle in 4 smaller 
				\end{itemize}
			\end{itemize}
			\item For more see reader
		\end{itemize}

\section{Advanced 3D Data Structures}
	\subsection{Introduction}
		\begin{itemize}
		\item Motivation
			\begin{itemize}
			\item Diff data sources and apps need diff data reps
			\item Requirements must be met
			\end{itemize}
		\item 3D data structs requirements
			\begin{itemize}
			\item Exact rep of general obj
			\item Comb of objs
			\item Linear trans
			\item Interaction
			\item Fast spatial searches
			\item Mem capacity
			\item Fast rendering
			\end{itemize}
		\end{itemize}

	\subsection{Point Cloud}
		\begin{itemize}
		\item Usage: For fast and simple preview (from digitizer or 3d scanner)
		\item Specs
			\begin{itemize}
			\item Data structure: list of points (spatial coords)
			\item Transformations: t whole cloud by applying t on each point
			\item Combinations: combine clouds
			\item Memory Consumption: high mem for accurate reps
			\item Rendering
				\begin{itemize}
				\item Simple points rendering
				\item Depth buffer for correct occlusion
				\item Nowadays high complexity: polygons often smaller than screenpixel (point cloud more efficient)
				\end{itemize}
			\end{itemize}
		\item Pros
			\begin{itemize}
			\item Fast/easy rendering
			\item Exact repwith correct occlusion
			\item Fast/easy transformations
			\end{itemize}
		\item Cons
			\begin{itemize}
			\item Many points for complex surfaces
			\item High memory for that case
			\item Limited comb ops
			\end{itemize}
		\end{itemize}

	\subsection{Wireframe Model}
		\begin{itemize}
		\item Edges rep
		\item Used for constr of buildings
		\item Specs
			\begin{itemize}
			\item Data structure: list of edges, each edge has 2 verts, each vert has spatial coords
			\item Transformations: same as point cloud
			\item Combinations: Append point and edge lists
			\item Memory Consumption
				\begin{itemize}
				\item Vert may be starting point of many edges
				\item Lots of edges for curved surfs
				\end{itemize}
			\item Rendering
				\begin{itemize}
				\item For devices which only draw lines (vector displays/plotters)
				\item Not possible to eliminate hidden edges
				\item No hidden line method out of bare wireframe model
				\end{itemize}
			\end{itemize}
		\item Pros
			\begin{itemize}
			\item Fast rendering/Easy transformations
			\item Gen models by digitizing
			\end{itemize}
		\item Cons
			\begin{itemize}
			\item High memory for curved surfaces
			\item Restricted comb possis
			\item Inexact due to line approximation of curves (no surfs, no occlusion)
			\end{itemize}
		\end{itemize}

	\subsection{Boundary Representation (B-Rep)}
		\begin{itemize}
		\item List of faces, all objs rep by boundaries, closed unit
		\item Add face info for fast rendering (normals, tangents,...)
		\item Not exact rep since polygons
		\item Usually only planar polygons
		\item Find neighbor polygons fast
		\item Similar alternative: Winged-edge data structure (edges central)
			\begin{itemize}
			\item Starts with edges, each edge has pointer to 2 faces and pointer to succ and pred edges of face
			\item Fast neighboring searches possible, but more pointers
			\end{itemize}
		\item Specs
			\begin{itemize}
			\item Data structure
				\begin{itemize}
				\item List of faces.
				\item Face has list edges.
				\item Edge has two vertices.
				\end{itemize}
			\item Transformations: Same but add per face info also transformed
			\item Combinations
				\begin{itemize}
				\item Simple clipping with plane
				\item Advanced ops (union, intersection,difference) addsematic needed
				\item Each B-Rep object closed (normals pointing outward)
				\item Possible combination algorithm:
					\begin{itemize}
					\item Cut polygons of A with polygons of B
					\item Speed up with bboxes (rough intersection test), exact int only when needed
					\item Convex polygons only is better
					\item Classifly polygons of A (inside, outside, on surface) to polygons of B
					\item Inside/Outside test: shoot ray along normal
					\item Nearest polygon is considered inside/outside depending on normal dir 
					\item Points of faces have same classification until border points appear
					\item Add pointers for classification inheritance
					\item Depending on the operation remove polygons/merge both objects
					\end{itemize}
				\end{itemize}
			\item Memory Consumption
				\begin{itemize}
				\item Add memory consumption due to faces small
				\item Subdivision for curved surfaces: high mem
				\item Add links in vert list between neighbor points with smale classification
					\begin{itemize}
					\item Parametrizable surfaces (free form surfaces, quadrics, superquadrics): param space is subdivided into pieces, approxby planar polygons (high mem for high subdiv)
					\item Non-parametrizable surfaces (non-planar polygons): Non-planar polygons are tesselated recursively until approx is good (threshold for normal vector diff between faces)
					\end{itemize}
				\end{itemize}
			\item Rendering: Needs alg which handles hidden lines/surfs
			\end{itemize}
		\item Pros
			\begin{itemize}
			\item Trans easy
			\item Arbitrary closed objects
			\end{itemize}
		\item Cons
			\begin{itemize}
			\item High mem const when tesselatd/subdivided
			\item Combs not easy/cheap
			\item Curved surfaces need approx
			\end{itemize}
		\end{itemize}

	\subsection{Binary Space Partitioning Tree (BSP tree)}
		\begin{itemize}
		\item Special B-Rep type for static scenes, polygons def sep plane which partition the space
		\item Simplifies rendering by easier/faster sorting of polygons
		\item Drawn back to front (correct occlusion, transparency)
			\begin{itemize}
			\item Data structure
				\begin{itemize}
				\item Pointer to root node (planar polygon), node points to two child nodes
				\item Left/right subtree: in front of poly/behind poly
				\item Intersecting polys are cut
				\item Inclusion test of vertex easy, traverse tree: if last step is right step point in object
				\item Construction
					\begin{itemize}
					\item Linear list if convex obj
					\item Else convert face list of B-rep into BSPtree 
					\item Search poly which intersects the fewest other polys with sep plane (rnd select polys for that)
					\item Subdivide face list
					\item Poly from step 1 is root, others are the left and right subtrees
					\end{itemize}
				\end{itemize}
			\item Transformation: All vertices, per face info plus plane equations transformed
			\item Combinatons
				\begin{itemize}
				\item Either combine B-rep of obj and constr BSP tree or combine directly (faster)
				\item Polygon $P_{A}$ (root node of object A) intersected with object B
					\begin{itemize}
					\item $P_{A}^{in}$ .. part of $P_{A}$ inside object B
					\item $P_{A}^{out}$ .. part of $P_{A}$ outside object B
					\end{itemize}
				\item Separation plane of $P_{A}$ is used to separate object B into two parts
					\begin{itemize}
					\item $B^{-}$ .. Part of B behind the separation plane
					\item $B^{+}$ .. Part of B in front of the separation plane
					\end{itemize}
				\item Root of the new BSP tree object is the separation plane and depending on the operation $P_{A}^{in}$ (intersection) or $P_{A}^{out}$ (union and differnce) as polygon
				\item The subtrees of C are generated recursivly
					\begin{itemize}
					\item $C_{l}$ = $A_{l}$ op $B^{-}$
					\item $C_{r}$ = $A_{r}$ op $B^{+}$
					\end{itemize}
				\item Recursion stops if one of the two operands represents a homogenous subtree
				\end{itemize}
			\item Memory comparable to B-Rep since same lists
			\item Fast rendering with correct occlusion 
				\begin{itemize}
				\item Painter's algorithm (back to front rendering)
				\item Draw all polygons not in half-space of the viewpoint (left or right subtree)
				\item Draw root and then other subtree
				\end{itemize}
			\item Pros
				\begin{itemize}
				\item Fast rendering with correct occlusion, 
				\item Easy transformations
				\item Arbitrary objects
				\item Combinations faster than B-Reps
				\item Model gen on digitized models possible
				\item Fast search
				\end{itemize}
			\item Cons
				\begin{itemize}
				\item Curved surfaces approximated
				\item Only convex polygons used
				\item High memory for curved/complex objects
				\end{itemize}
			\end{itemize}
		\end{itemize}

	\subsection{kD Tree}
		\begin{itemize}
		\item Special case of BSP tree (axis-aligned subdivision)
		\item Inner nodes are axis altering sep planes, polygons only in leaf nodes (may be cut in pieces)
		\item Faster kD Tree gen due to axis aligned sep planes but simple inside/outside test of BSP tree lost
		\end{itemize}

	\subsection{Octree}
		\begin{itemize}
		\item Rep volume in data structure
		\item Fast/easy comb of objects, not necessary in the rendering process (also faster/easier)
		\item Each octree node is region in space, if nevessary region subdivided into 8 subspaces
		\item Subdivision done through center of space along main axes
		\item Each leaf is a block (empty white (W) block, full black (B) block)
		\item If rep not accurate (gray (G) block), further subdivision
		\item Gray blocks are subdivided until they are good enough
		\item Specs
			\begin{itemize}
			\item Diff transformation, tree rebuild after every trans (specific t like 90deg rot simple)
			\item Fast/easy comb
			\item High memory for curved and complex surfaces
			\item Rendering
				\begin{itemize}
				\item Renders farthest subspace first until closest subspace (correct occlusion)
				\item If W node, do nothing
				\item If F node, draw cube
				\item If further subdiv, order leaf nodes relativ to view point and render recursively
				\end{itemize} 
			\item Pros
				\begin{itemize}
				\item Fast/easy comb
				\item Easy rendering
				\item Fast spatial searches
				\item Model gen through digitization possible
				\end{itemize}
			\item Cons
				\begin{itemize}
				\item High mem
				\item Hard transformations
				\item No exact rep(only cubes rendered)
				\end{itemize}
			\end{itemize} 
		\end{itemize}

		\subsubsection{Extended Octree}
			\begin{itemize}
			\item New leaf nodes: Face, edge, vertex nodes
			\item Allows more details without further subdiv
			\item Octree gen out of faces and edges (similar to B-Rep)
				\begin{itemize}
				\item Separate lists in 8 sublists for each octant by clipping with borders between octants
				\item For each octant
					\begin{itemize}
					\item If both lists empty: node is either full or empty
					\item If vert list contains one vertex: gen vert node
					\item If face list contains two faces: gen edge node
					\item If face list contains one face: gen face node
					\item Else subdivde octant
					\end{itemize}
				\end{itemize}
			\item Specs
				\begin{itemize}
				\item Data struct: Full, empty, edge, vert or face node or p to 8 subnodes
				\item Trans: Convert into B-Rep, t and convert back
				\item Comb
					\begin{itemize}
					\item If nodes are either full or empty: apply operation
					\item If nodes are subdivided then all subnodes are combined
					\item If node of A is either E,V or F and B is G then subnodes of B are combined with the node of A
					\item If nodes of A and B are either E, V or F then the resulting combination is calculated geometrically
					\end{itemize}
				\item Memory: Lower for complex objs than usual octree
				\item Rendering: Convert back to B-Rep
				\item Pros
					\begin{itemize}
					\item Memory consumption lower
					\item Better rep of arb objects due to new nodes
					\end{itemize}
				\item Cons:
					\begin{itemize}
					\item Conversion to B-Rep
					\item Combination of two extended octrees more complicated
					\end{itemize}
				\end{itemize}
			\item Octree as spatial dirs
				\begin{itemize}
				\item Often used as search struct for diff objs combined in a scene
				\item Important for computer games (collision detection)
				\item Nearest neighbor to curr obj fast
				
				\end{itemize} 
			\end{itemize}

	\subsection{Constructive Solid Geometry Tree (CSG Tree)}
		\begin{itemize}
		\item Binary tree, with logical (comb) intermediate nodes, leafs contain primitives (spheres, blocks, sweeps, ...) and their trans
		\item Specs
			\begin{itemize}
			\item Transformation: Add trans to the leaf node
			\item Comb: Attach both trees as subtrees to a new root node with desired operation
			\item Memory: Efficient exact representation of complex objs
			\item Rendering
				\begin{itemize}
				\item Directly not possible
				\item Convert to B-Rep (exact rep gets lost)
				\item Ray tracing for rendering (slower)
				\end{itemize}
			\item Pros
				\begin{itemize}
				\item Low mem
				\item Exact rep
				\item Easy comb and trans
				\item Fast spatial searches
				\end{itemize}
			\item Cons
				\begin{itemize}
				\item Rendering more complicated
				\item Not easy to gen a CSG tree out of digitized data
				\end{itemize}
			\end{itemize}
		\end{itemize}

	\subsection{Bintree}
		\begin{itemize}
		\item Binarytree used for spatial searches
		\item Recursive perpendicular subdivision (altering axes)
		\item Optimized irregular subdivison, fewer nodes than octree 
		\item Intermediate nodes contain subdiv pos (values $\in [0,1]$), leaf nodes geometry
		\end{itemize}

	\subsection{Grid}
		\begin{itemize}
		\item Regular subdivision
		\item Only one lew (non-tree struct), cells addressed directly (neighboring rel)
		\item Flexible data types
		\item Cell size important (accuracy)
		\item Hierarchical grids: Base struct consists of large cells, finer cells where needed
		\item Specs
			\begin{itemize}
			\item Trans: difficult, must be recomputed (90deg rot simple,...)
			\item Comb
				\begin{itemize}
				\item No geometric info, but MIN,MAX,DIFF ops available
				\item Grid resolution must fit
				\end{itemize}
			\item Memory Consumption: depends on grid res
			\item Rendering: Suitable for algs which frequently sample neighboring cells during rendering process (raycasting)
			\item Pros
				\begin{itemize}
				\item Constant processing time of cells
				\item Mem dependent on res
				\item Can be used to rep digitized objects
				\end{itemize}
			\item Cons
				\begin{itemize}
				\item No geometrical info about object
				\item High mem for accurate rep
				\item Hard trans
				\end{itemize}
			\end{itemize}
		\end{itemize}

\section{Sampling}
	\subsection{Signals and Functions}
		\begin{itemize}
		\item Signal as function (often temporal/spatial domain) that conveys info
		\item Continuous/discrete signals (analog/digital sources)
		\item Selecting finite set of values from signal is sampling
		\item Attempt to recreate orig continuous signal is reconstruction.
		\end{itemize}

	\subsection{Nyquist frequency}
		\begin{itemize}
		\item Uniform sampling big errors, what is best sampling freq?
		\item Nyquist frequency: Sampling above two times the highest freq of function
		\item Aliasing 
			\begin{itemize}
			\item High frequencies masquerading as low frequencies
			\item Use low-pass filter before sampling process to reduce nyquist freq (also sampling data reduced)
			\end{itemize}
		\item Sampling in CG: Projection of 3d data on 2d image plane
		\item Point Sampling
			\begin{itemize}
			\item Select point for each pixel, evaluate signal at point and assign value to pixel
			\item Supersampling: sampling at a higher rate.
			\end{itemize}
		\item Area sampling
			\begin{itemize}
			\item Unweighted area sampling
				\begin{itemize}
				\item Define grid
				\item On each grid point evaluate average intensity of square
				\item Problems with small objects in the square area
				\end{itemize} 
			\item Weighted area sampling: Objects contribution weighted accord to dist
			\end{itemize}
		\end{itemize}

	\subsection{Sampling Theory}
		\begin{itemize}
		\item Frequency domain: signal as sum of sine waves (phase shiften, diff freqs and amplitudes)
		\item Fourier analysis (FA): determine which sine waves must be used
		\item Fourier transform (FT): switch from spatial to frequency domain vice versa
		\item F(u): function in freqdomain, F(u) how much the freq u appears in orig signal (amplitude, phase shift)
		\item F(u) is the rep of f(x) in the frequency domain
		\item FT of a continuous, integrable signal f(x) is defined by: 
		$$F(u) = \int_{-\inf}^{+\infty} f(x)[\cos 2 \pi u x - i \sin 2 \pi u x] \delta x$$
		\item For each u, the value F(u) is a complex number $R(u) + iI(u) $, encoding phase shift and amplitude of the freq u component of signal
		\item Amplitude (magnitude) of F(u) is defined by: $\left|F(u)\right| = \sqrt{R^2(u) + I^2(u)}$
		\item Phase shift (phase angle) is given by: $$ \phi(u) = \tan^{-1}\left[\frac{I(u)}{R(u)}\right]$$
		\item Choosing high sampling rate for discrete FT, good approximation of continuous FT is obtained
		\item Fast FT may be used to convert to the frequency domain.
		\item Alternatives: Hartley transform, wavelet transform.
		\end{itemize}

	\subsection{Low-Pass Filtering}
		\begin{itemize}
		\item Remove problematic high frequencies from the orig signal to recon orig signal from finite samples
		\item Bandwidth limiting, band limiting, low-pass filtering means lower nyquist freq
		\end{itemize}

		\subsubsection{Convolution and Convolution Theorem}
			\begin{itemize}
			\item Two functions in spatial domain are convolved their frequency domain rep are multiplied and vice versa
			\item $f_1 * f_2 \equiv F_1F_2$ and $F_1*F_2 \equiv f_1f_2$
			\item FT and multiplication can be much cheaper than convolution in spatial domain
			\item Perfect low-pass filter in frequency domain is multiplication with a box filter, which is conv with sinc function in spatial domain
			\item Sinc has infinite support, therefor non-ideal truncated sinc alternatives are used
			\end{itemize}

	\subsection{Reconstruction}
		\begin{itemize}
		\item Sampling
			\begin{itemize}
				\item Mult with comb func (1 in sampling points) in spatial domain
				\item Conv with FT of comb in freq domain
				\item FT comb is another comb with teeth at other posis
			\end{itemize}
		\item Sampling below nyquist freq means the teeth of comb are too far apart in spatial domain and to close together in frequency domain (overlapping - aliasing)
		\item Reconstruction means: eliminate shadow spectra and retain original spectrum (multiplication with box filter in freq domain)
		\item In spatial domain this corresponds to a convolution with the sinc filter (ideally)
		\item Non-ideal reconstruction causes two types of aliasing
			\begin{itemize}
				\item Orig spec not entirely coverd (high freqs damped)
				\item Shadow spec not fully eliminated (erroneous high freqs)
			\end{itemize}
		\item Used recon filters
			\begin{itemize}
				\item NN
				\item Linear int
				\item Symmetric cubic filters
				\item Windowed Sinc
			\end{itemize}
		\end{itemize}

\section{Texturing}
	\subsection{Introduction}
		\begin{itemize}
		\item Diff material props: Color, Reflection, Gloss, Transp, Bump
		\item Texture gradient 3 props: size, shape, density (defines amount of deformation of pattern)
		\item Texture mapping: map tex coords on obj space coords, finally obj space coords mapped to img space
		\item Parametrization must be defined
		\item Perspective correctness
			\begin{itemize}
			\item Affine tex mapping directly interpolates texture coords between two endpoinds 
			\item Perspective correct mapping interpolates after dividing by depth value, then uses interpolated reciprocal to recover correct coords
			\end{itemize}
		\end{itemize}

	\subsection{Types of Textures}
		\begin{itemize}
		\item Mostly 2d regular grid storing texels (bitmap, etc..)
			\begin{itemize}
			\item High mem, slow tex fetch, parametrization needed, aliasing
			\end{itemize}
		\item Also general texture defs: 1d, 2d, 3d (mostly volume rendering),...
		\item Scanline Oriented Mapping
			\begin{itemize}
			\item Scanline oriented rendering calcs img line by line
			\item Texture loopup of line needed (texture scanning)
			\end{itemize}
		\item Procedural and Solid Texturing
			\begin{itemize}
			\item Gen tex on the fly per fragment
			\item Fast eval, but limited variety
			\item 3d parameter space, therefore no parametrization needed, undeformed texture
			\item Solid texturing: gen function evaluated over $\mathbb{R}^3$ at surf
			\end{itemize}
		\item Environment Mapping
			\begin{itemize}
			\item Tex def as surrounding env
			\item Project env map on surrounding hull/cube/sphere/cylinder of obj (view rays from center of obj)
			\item Polar coord def: better texels access
			\item For reflective surf, intersection of reflected ray def surf value
			\item For dif surf lowpass filter needed (scattered light of diffuse reflec)
			\item Projection step different for each environment map
				\begin{itemize}
				\item Cube map: perspective distortion is taken into account
				\item Sphere: raytracing (no reflected rays)
				\end{itemize}
			\end{itemize}
		\item Bump Mapping
			\begin{itemize}
			\item Tex spec as height field, new normals derived
			\item Does not change geometry of obj, just influence shading
			\end{itemize}
		\item Horizon Mapping
			\begin{itemize}
			\item For each texel n horizon values calced before and interpolated when shading
			\item Point in obj space only lit when dir to light src higher than pre-computed horizon
			\item Bumps are casting shadows, bumps below shadow horizon are not falsly lit
			\end{itemize}
		\item Parallax Mapping
			\begin{itemize}
			\item Displace text coord at surf point by a func of view angle in tangent space (angle rel to surf normal) and val of height map at that point
			\item At steeper view angles, tex coords displaced more (effect of depth due to parallax)
			\item Texture loopup pos altered
			\item Occlusions cannot be modelled
			\end{itemize}
		\item Relief Mapping
			\begin{itemize}
			\item More accurate alternative to parallax mapping
			\item Short-dist raytracing done in pixel shader
			\item Self occlusion, self shadowing, view-motion parallax and silhouettes
			\item Acceleration techniques possible
			\end{itemize}
		\end{itemize}

	\subsection{Anti-aliasing}
		\begin{itemize}
		\item Texture mapping, deformation of size, moire-patterns or pixelization artefacts
		\item Pixel covered by many texels
			\begin{itemize}
			\item Choosing just one texel false
			\item Weighted averaging better (direct convolution during texel eval, or prefiltering)
			\end{itemize}
		\item Direct convolution
			\begin{itemize}
			\item Simple covering shapes used for averaging
			\item Computationally expensive but superior quali than NN
			\end{itemize}
		\item Mip-mapping
			\begin{itemize}
			\item Prefiltering, diff resolution of texture precalced (half size each step)
			\item One third additional storage
			\item Mipmap level must be determined when mapping
			\item Trilinear int: interpolation between mip map levels
			\end{itemize}
		\item Summed area table
			\begin{itemize}
			\item Sum of rects calced before
			\item Access sum of certain rect region in constant time
			\item Not used for high precision texts (sum becomes to big)
			\end{itemize}
		\end{itemize}



\section{Illustrative Visualization}
	\subsection{Introduction}
		\begin{itemize}
		\item Bild mit Absicht Wissen zu vermitteln (Komplexe Zusammenhänge von Strukturen oder Abläufen)
		\item Abstraktion(Verzerrung Realität/Model) um visualle Überladung zu verhindern
		\item Verwendet Stilmittel und fokusiert auf Thema (Focus/Context)
		\item Verschiedene Abstraktionebenen (Illustrator wählt Abstraktionmittel)
		\end{itemize}
	\subsection{Abstraktions Ziele}
		\begin{itemize}
		\item Darstellung Form/Struktur
		\item Hervorstreichung/Verminderung von Objekten
		\item Vereinfachung
		\item Künstlichkeit darstellen
		\item Sichtbarkeit von Objekten sicherstellen
		\item Räumlichen Überblick
		\item So detailiert wie nötig, so einfach wie möglich
		\end{itemize}
		
	\subsection{Low-Level Abstraktionstechniken}
		\begin{itemize}
		\item Wie wird etwas dargestellt?
		\item Stilisierung
			\begin{itemize}
			\item Silhouetten/Konturen
			\item Bleistift/Tusche
			\item Punktiert (stippling)
			\item Strichliert (hatching)
			\item Metallisch/Farbton shading
			\item Echtzeit strichlierung
			\item Suggestive contours
			\item Curvature-based ridge and valley enhancement
			\end{itemize}
		\item Volumen rendering, style transfunc ordnet voxel farbe und transp zu
		\item Lit Sphere Maps kann belichtung ersetzen
		\end{itemize}

	\subsection{High-Level Abstraktionstechniken}
		\begin{itemize}
		\item Was soll dargestellt werden ("Smart visibility")
		\item Sichtbarkeit durch Relevanz bestimmt
		\item Bsp
			\begin{itemize}
			\item View-dependent transp
			\item Cutaways and breakaways(verborgene Strukturen zeigen)
			\item Volume splitting: Kopf
			\item Hybrid Visibility Composting
			\item Importance-driven feature enhancement
				\begin{itemize}
				\item Relevanz Spez, Relevanz Composting, Opacity niveau
				\item Betonung explizit gewählten features
				\end{itemize}
			\item Illustrative Context-Perserving Exploration
				\begin{itemize}
				\item Implizite Betonung von relevanten Features
				\item Ghosting ("Magic lamp"): innere und äußere gleichzeitig
				\end{itemize}
			\end{itemize}
		\item Explosionsdarstellung
			\begin{itemize}
			\item Techn. illustration, Bauanleitung
			\item Transformieren von verdeckenden Strukturen
			\item Ablauf
				\begin{itemize}
				\item Focus selection
				\item Def von Teilstrukturen
				\item Layoutgenerierung
				\item Rendering
				\end{itemize}
			\item Automated Gernation of Interactive 3d exploded view diagrams
			\item Explosion mit/ohne Randbedingungen
			\end{itemize}
		\item VolumeShop: Interaktive App Illustrationen aus Volumendaten
		\item Multi-Object Volume Rendering
			\begin{itemize}
			\item 3 Obj: Auswahl (gewählte, evtl transformierte region), Ghost (gewählte region in orig pos), Hg
			\item Darstellungen von einzelnen Obj und Überschneidungen mittels 2dim Transferfunktionen
			\end{itemize}
		\item Illustrative Beleuchtung: Verschiedene Stile mittels Beleuchtungstransferfunktion, Stile für Hg, Auswahl und Ghost
		\item Selektive Illustration
			\begin{itemize}
			\item Smart vis: view-dep cutaways und ghosting
			\item Interactive importance-driven vol rendering
			\item Ghosting: opazität von verdeckenden Strukturen selektiv vermindert
			\item Pfeile, Fächer, Annotationen
			\end{itemize}
		\end{itemize}

\section{Visualisierung}
	\begin{itemize}
	\item Siehe Visualisierung Zusammenfassung (Visualisierung Gröller, Onur Dogangönül)
	\end{itemize}

\end{document}
