Arithmetic/Logic Unit Shifter

Ronald Reagan

Description

Computer Principles Advanced Compiler Research Laboratory School of Computer Science & Engineering Seoul National University Arithmetic/Logic Unit & Shifter

• national university computer principles
• floor value if the result
• advanced compiler research laboratory school
• integer floor
• logic circuit
• data input
• computer science
• computer-science

Sujets

• Computer
• University
• National
• Research
• Integer

Informations

• Publié par: phawyir
• Nombre de lectures: 15
• Langue: English
• Poids de l'ouvrage: 6 Mo

Extrait

Unstructured Computational Meshes for
Subdivision Geometry of ScannedGeological
Objects
1 2 1Andrey A. Mezentsev Antonio Munjiza and John-Paul Latham
1 DepartmentofEarth Sciences and Engineering, Imperial College London,
London, UK (A.Mezentsev),(J.P.Latham)@imperial.ac.u k
2tofEngineering, Queen Mary University of London,London, UK
[e-mail]
Summary . This paper presents ageneric approachtogeneration of surface and
volumeunstructured meshes for complex free-form objects, obtained by laser scan -
ning. Afour-stage automated procedure is proposed for discrete data sets: surface
mesh extraction from Delaunaytetrahedrization of scanned points, surface mesh
simplification,definition of triangular interpolating subdivision faces, Delaunayvol-
umetric meshing of obtained geometry.The mesh simplification approachisbased
on the medial Hausdorff distance envelopebetween scanned and simplified geomet-
ric surface meshes. The simplified mesh is directlyused as an unstructured control
mesh for subdivision surface representation that preciselycaptures arbitrary shapes
of faces, composing the boundary of scanned objects. CAD model in Boundary Rep-
resentation retains sharp and smooth features of the geometry for further meshing.
Volumetric meshes withthe MezGen code are used in the combined Finite-Discrete
elementmethods for simulation of complex phenomenawithin theintegrated Virtual
Geoscience Workbenchenvironment(VGW).
Key words: laser scanning, unstructured mesh, mesh simplification, subdivision
surfaces
1Introduction
Recentdevelopments in the Finite Elementmethod(FEM) and advances in power
of affordable computers have broadened the FEM application area to simulation
of complex coupled phenomena in natural sciences, geology,biology andmedicine
in particular [Zienkiewicz]. The formulation of the combined Finite-Discrete ele-
mentmethod(FEM-DEM) in thenineties[Munjiza] has established aconnection
between the continuous and discrete modeling of complex coupled phenomena. Such
aformulation opens apossibility for developmentofintegrated Virtual Prototyp-
ing Environments (VPE) in natural sciences, similar the VPE found in engineering
[Latham].74 A. A. Mezentsev et al.
VPE is typically aunification of highlyinhomogeneous interacting computa-
tional components, representing the modelsondifferent levels of mathematicalab-
straction. Forthe success of VPE in natural sciences it is highlydesirabletoprovide
unified means for model representationondifferent levels of the modelsabstrac-
tion: the so-calledmicroand macro levels (sometimes also addressed as Mechanics
of Continua and Discontinua) [Munjiza],[Latham]. Foramicrolevel of simulation
the model approximates continuous fields of system variables and systems of partial
differential equations form the mathematical model.Onmacro level of simulation
discontinuous fields of systems variables are approximated by the model and mathe-
matically arerepresented by systems of ordinary or differential-algebraicequations.
The FEM-DEM methodisaunique computational technology,which permits repre-
sentation on differentlevels of modeling to be combined: both micro level and macro
level. Methodologicallyitprovides aunified framework for simulationswithin the
framework of natural sciences VPE.
Asastarting pointfor simulation, both the FEM and the DEM require domain
discretisation intoaset of geometrical simplicies-amesh. Formanynatural sciences
applications, and specifically in geology,the main problem, making the workflowvery
complex, is related to absence of fullyautomatic methods of geometry definition and
meshing. Most of the natural objects, i.e.geological particles or bio-medical entities,
are characterized by complex shapethat can only be capturedwith sophisticated
scanning equipment. With increasing robustness of scanning technology it is has
become possibletouse realistic point-wisescanned data to define natural object ge-
ometries for simulations. Unfortunately, the output from scanned data is not usable
directly formeshing and there has been much recentresearchreported in the area
of process automation (see, for example, [Bajaj] –[Xue]).
It should be stressed that geometry definition and downstream computational
mesh generation are very application specific. Moving to anew application area
generally requires developmentofanew geometric model with differentparameters,
meeting specific requirements of downstream applications. Importantly,most of the
developed geometric formatsdonot fullyaddress discretisation requirements from
the pointofview of theefficiency of organization and application in the VPE,
pursuing rather conflicting requirements for geometric models. The presentpaper
addresses this problem from the pointofview of CAD/mesh integration for the
Virtual Geoscience Workbenchenvironment(VGW) in natural sciences, reflecting
agrowing shift from stochastic to deterministic models in geological simulations.
Therest of the paper is organized as follows. In Section 2the automatic meth-
odsfor geometric models derivation based on discrete data are discussed together
with basic principles of subdivision surfaces. In Section3anew mesh simplification
concept using medial Hausdorff distance is presented. In Section4numerical results
are given, whileSection5gives future work and conclusions.
2CAD Definition from Discrete ScannedData
With the development of new scanning technology it is nowpossibletocreate large
data bases of point-wise data in differentareas of science and engineering. Increased
accuracy of scanning permits acquisition of data sets, containing millions of data
points andpreciselydefining the shapeofdifferent objects. Unfortunately,this in -
formation cannot be directlyused in the process of the computational model defi-Computational Meshes forSubdivision Geometry of Scanned Objects 75
nition. The size of data sets dictates developmentofautomatic conversion methods
of scanned data to geometric and further to computational models. This problem
has received in recentyears alot of attention in computer vision, computational
geometry and mesh generation communities [Bajaj]–[Xue].
Typically,geometry of scanned objects is defined by the boundary,using dif-
ferentincarnations of the so-called Boundary Representation (BREP) model. The
BREP model combines surfaces with elements of topology,organized inatree form
(see, for example, [Mezentsev]–[Lang]). Most popular choices for faces underlying
representation in BREP are piecewise polyhedralmeshes [Owen] or spline surfaces,
approximating discrete data [Lang].Asscanned data sets contain redundantdata
points,not corresponding to the underlying geometric complexity of the objects,
initialdiscrete data requiressimplification in most cases. Scanneddiscrete represen -
tation also greatly differs from application area to application area, and it changes
significantly with the scanning technology used, so it is necessary to define specifics
of considered input data sets.
2.1Specifics of Scanned Data and Geometryinthe Geological
Applications
The developmentofahighly automatedmethodofconverting scanned data to sur-
face geometry is considered. It should work with clouds of points,organized as un-
structured set of X, Y,Zcoordinates, type of data is common for reverse engineering,
image recognition and computer visualization problems [Bajaj],[Frey]. It does not
have ordered sub-parallel sliced structure, frequently found in the tomography-based
bio-medical applications [Cebral]. In the considered case, the data consists ofadense
bounded noisy cloud of points, lyingonthe boundary of the domain (see, for example
Fig.1and Fig. 2). The discrete data have the following features [Frey]:
1. Data maybevery noisy
2. Data sets are very dense (Fig. 2)
3. Straightforward approaches (like Marching Cubes [Lorensen]) frequently in -
troduce errors of polygonal approximation, theso-called staircase effects
4. Surface reconstruction algorithms are not targeted to produce computational
meshes, so the quality of meshes is low.
Addressing the specifics of the objectsunder consideration, it could be observed,
firstly,that geological particlegeometry is constrained, but not limited to asingle-
connecteddomain. It is mostly convexwith random combinations of smooth rounded
C and highlyirregular regions with sharp C edges. The set up of the problem has1 0
clearlydifferent geometry requirements in manyother application areas. Secondly ,
data is very noisy and it is likely to have isolated scanneddata points largely off-set
from the reconstructed surface. Thisfeature requires special measures to be taken
to insurestabilityofsurface reconstruction and simplification.
The problem of surface from extremelynoisy data is far from
solved andanumberofresearchpapers have been published recently,addressing spe-
cific typesofsmooth surfaces in certain application areas (see, for example[Kolluri]).
However, none of the papers address geological geometry,whichrequires reconstruc-
tion for the complete hull without unresolved areas, i.e. lowerpart of the geometry .
Thirdly, specifics of the usage of the geometrical model in the VPE simultane-
ously require efficiency of the geometry storage, access, rendering and meshing for76 A. A. Mezentsev et al.
Sharp edge
Curved smooth
region
Fig. 1. Typical particlegeometry as acombination of curved smooth and non-
smooth sub-regions with s