CM0304 Graphics I Graphics Hardware I.1 Graphics Systems
CMT107 Visual Computing
Copyright By PowCoder代写 加微信 powcoder
III.1 Object Representation
Xianfang Sun
School of Computer Science & Informatics
Cardiff University
➢Constructive solid geometry
➢Boundary representation
➢Mesh representation
• Rendering meshes with OpenGL
➢Volumetric representation: voxels
15:14 2CMT107 Visual Computing
Example Models and Scenes
15:14 3CMT107 Visual Computing
Geometric Modelling
15:14 4CMT107 Visual Computing
➢Need data-structures and algorithms to model shapes
• Scene – description of the whole environment
• Model – description of an object in the environment
• Suitable for creating, editing, analysing and rendering
➢Object representations
• Constructive solid geometry (CSG)
• Boundary representation (B-rep)
• Mesh representation
• Volumetric representation: voxels
Constructive Solid Geometry
15:14 5CMT107 Visual Computing
➢Use set of volumetric primitives
• Block, Tetrahedron, sphere, cylinder, cone, …
➢ Construct objects using Boolean operations
• Union, intersection, difference
15:14 6CMT107 Visual Computing
➢ CSG operations stored as tree (or sequence) of
operations on primitives
➢ Common for CAD – feature based modelling
Boundary Representation
15:14 7CMT107 Visual Computing
➢ Explicitly represent boundary of object:
• Basic elements are (natural) faces,
edges, vertices with a geometry
• Also record topology (connectivity/
boundary relations) of elements
➢Mathematically: an algebraic complex
(topology) with a geometric
realisation (geometry)
➢ Algorithmically: a graph data structure
(topology) where nodes have
shape (geometry) attributes
B-Rep: An Algebraic Complex
15:14 8CMT107 Visual Computing
B-Rep Geometry
15:14 9CMT107 Visual Computing
➢ Describe shape of each face, edge and vertex
• Vertex geometry: position
• Edge geometry: curve
E.g. straight line, circle, ellipse, free-form curve, . . .
• Face geometry: surface
E.g. plane, sphere, cylinder, cone, torus, free-form, . . .
B-Rep Data Structure
15:14 10CMT107 Visual Computing
➢B-Rep graph data structure representing the topology:
BODY Solid made of a list of LUMPS
LUMP Connected volume, bounded by a list of SHELLS
SHELL Connected surface, consisting of a list of FACES
FACE Natural surface, bounded by a LOOP
LOOP Connected curves, consisting of a list of COEDGES
Directed edge as part of a loop, consisting of an
EDGE (also called half-edge)
EDGE Natural edge, bounded by VERTICES
VERTEX Boundary of an edge
B-Rep Issues
15:14 11CMT107 Visual Computing
➢ Consistency of geometry and topology
• No explicit way to ensure boundary relations are
preserved by geometry
➢ Ambiguous and impossible models
• Topology allows us to determine impossible models
• Orientation and topology distinguish ambiguous models
B-Rep Orientation
15:14 12CMT107 Visual Computing
➢ Orient face: distinguish between inside and outside
• Surface normals always point towards the outside
➢ Orient each loop
• Move around each loop such that the inside lies to
the left when viewed from outside the model
• COEDGEs indicate direction of loop by ordering edge
end-points
• EDGE lies on two faces as indicated
by two COEDGEs
➢ Non-manifold objects: EDGE can lie
on more than two faces
• Causes problems for orientation, etc.
(so not allowed in standard B-rep)
Mesh Representation
15:14 13CMT107 Visual Computing
➢ Describe model as a polygonal mesh (often triangular)
• Collection of polygons (facets)
• Similar, but simpler than B-rep
• Linear approximation of object
• Fast and quality good enough for real-time rendering
15:14 14CMT107 Visual Computing
➢ Polygons are specified by a sequence of vertices
➢ Polygons are not just line segments, but have an interior
• Simple polygon: lines do not intersect
• Convex polygon: given two points inside the polygon,
the line segment joining the points lies inside polygon
• Flat polygon: polygon lies in a plane
➢ Orientation / sidedness:
• Polygons have a front and a back
• If vertices are in anti-clockwise order on display, we
see the front
(default OpenGL convention; consistent with B-rep
orientation)
Polygon Normal
15:14 15CMT107 Visual Computing
➢ If a polygon is simple, convex and flat, its normal can be
calculate using any 3 non-collinear points pl , pm, and pn
• Suppose l