Unlike image or text domains that benefit from an abundance of large-scale datasets, point cloud learning techniques frequently encounter limitations due to the scarcity of extensive datasets. To overcome this limitation, we present Symmetria, a formula-driven dataset that can be generated at any arbitrary scale. By construction, it ensures the absolute availability of precise ground truth, promotes data-efficient experimentation by requiring fewer samples, enables broad generalization across diverse geometric settings, and offers easy extensibility to new tasks and modalities. Using the concept of symmetry, we create shapes with known structure and high variability, enabling neural networks to learn point cloud features effectively. Our results demonstrate that this dataset is highly effective for point cloud self-supervised pre-training, yielding models with strong performance in downstream tasks such as classification and segmentation, which also show good few-shot learning capabilities. Additionally, our dataset can support fine-tuning models to classify real-world objects, highlighting our approach’s practical utility and application. We also introduce a challenging task for symmetry detection and provide a benchmark for baseline comparisons. A significant advantage of our approach is the public availability of the dataset, the accompanying code, and the ability to generate very large collections, promoting further research and innovation in point cloud learning.

Given a 3D point cloud, we propose a method for suitably resampling the cloud while reconstructing and preserving the feature curves to which some points are identified to belong. The first phase of our strategy enriches the cloud by approximating the curvilinear profiles outlined by the feature points with piece-wise polynomial parametric space curves through the use of the Hough transform. The second phase describes how the removal of a point or its insertion can be performed without affecting the approximated profiles and preserving the enriched structure of the cloud. The combination of the two steps provides multiple possibilities for processing a point cloud by varying its size or improving its density homogeneity without affecting the retrieved feature curves. The various capabilities of our approach are investigated to produce simplification, refinement, and resampling techniques whose effectiveness is evaluated through experiments and comparisons.

Feature curves are space curves identified by color or curvature variations in a shape, which are crucial for human perception (Biederman, 1995). Detecting these characteristic lines in 3D digital models becomes important for recognition and representation processes. For recognizing plane curves in images, the Hough transform (HT) provided a very good solution to the problem. It selects the best-fitting curve in a dictionary of families of curves through a voting procedure that makes it robust to noise and missing parts. Since 3D digital models are often obtained by scanning real objects and may have many defects, the HT has been extended to recognize and approximate space curves in 3D models that correspond to relevant features This work overviews three HT-based different approaches for identifying and approximating spatial profiles of points extracted from point clouds or meshes. A first attempt at this extension involved projecting the spatial points onto the regression plane, thus reducing the problem to planar recognition and using families of plane curves. A second approach has been proposed to recognize spatial profiles that cannot be projected onto the regression plane, using two types of space curve families. Unfortunately, the main drawback of methods based on traditional HT is that it requires prior knowledge of which family of curves to look for. To overcome this limitation, a third method has been developed that provides a piecewise space curve approximation using specific parametric polynomial curves. Additionally, free-form curves that a parametric or implicit form cannot express can be represented using this technique. In the paper, we also analyze the pros and cons of the various approaches and how they managed and reduced the HT's computational cost, given the large number of parameters introduced when families of space curves are considered.

Urban simulations that involve disaster prevention, urban design, and assisted navigation heavily rely on urban geometric models. While large urban areas need a lot of time to be acquired terrestrially, government organizations have already conducted massive aerial LiDAR surveys, some even at the national level. This work aims to provide a pipeline for extracting multi-scale point clouds from 2D building footprints and airborne LiDAR data, which depends on whether the points represent buildings, vegetation, or ground. We denoise the roof slopes, match the vegetation, and roughly recreate the building façades frequently hidden to aerial acquisition using a parametric representation of geometric primitives. We then carry out multiple-scale samplings of the urban geometry until a 3D urban representation can be achieved because we annotate the new version of the original point cloud with the parametric equations representing each part. We mainly tested our methodology in a real-world setting – the city of Genoa – which includes historical buildings and is heavily characterized by irregular ground slopes. Moreover, we present the results of urban reconstruction on part of two other cities, Matera, which has a complex morphology like Genoa, and Rotterdam.

Abstract We propose CurveML, a benchmark for evaluating and comparing methods for the classification and identification of plane curves represented as point sets. The dataset is composed of 520k curves, of which 280k are generated from specific families characterised by distinctive shapes, and 240k are obtained from Bézier or composite Bézier curves. The dataset was generated starting from the parametric equations of the selected curves making it easily extensible. It is split into training, validation, and test sets to make it usable by learning-based methods, and it contains curves perturbed with different kinds of point set artefacts. To evaluate the detection of curves in point sets, our benchmark includes various metrics with particular care on what concerns the classification and approximation accuracy. Finally, we provide a comprehensive set of accompanying demonstrations, showcasing curve classification, and parameter regression tasks using both ResNet-based and PointNet-based networks. These demonstrations encompass 14 experiments, with each network type comprising 7 runs: 1 for classification and 6 for regression of the 6 defining parameters of plane curves. The corresponding Jupyter notebooks with training procedures, evaluations, and pre-trained models are also included for a thorough understanding of the methodologies employed.

The problem faced in this paper concerns the recognition of simple and complex geometric primitives in point clouds resulting from scans of mechanical CAD objects. A large number of points, the presence of noise, outliers, missing or redundant parts and uneven distribution are the main problems to be addressed to meet this need. In this article we propose a solution, based on the Hough transform, that can recognize simple and complex geometric primitives and is robust to noise, outliers, and missing parts. Additionally, we can extract a series of geometric descriptors that uniquely characterize a primitive and, based on them, aggregate the output into maximal or compound primitives, thus reducing oversegmentation. The results presented in the paper demonstrate the robustness of the method and its competitiveness with respect to other solutions proposed in the literature.

Advances in modeling of discrete models have allowed the development of approaches for direct mesh modeling and modification. These tools mainly focus on modeling the visual appearance of the shape which is a key criterion for animation or surgical simulation. Most of the time, the resulting mesh quality as well as the semantics preservation capabilities are not considered as key features. These are the limits we overcome in this paper to enable fast and efficient mesh modifications when carrying out numerical simulations of product behaviors using the Finite Element (FE) analysis. In our approach, the modifications involve the resolution of an optimization problem where the constraints come from the shapes of the operating tools and the FE groups (sets of mesh entities) used to support the semantic information (e.g. boundary conditions, materials) contained in the FE mesh model and required for FE simulation. The overall mesh quality, a key point for accurate FE analysis, is guaranteed while minimizing an objective function based on a mechanical model of bar networks which smoothes the repositioning of nodes. Principle of the devised mesh operators is exemplified through the description of a 2D/3D mesh drilling operator. The proposed mesh modification operators are useful in the context of fast maintenance studies and help engineers to assess alternative design solutions aimed at improving the physical behavior of industrial machinery.

In digital geometry processing and shape modeling, the Laplace-Beltrami and the heat diffusion operator, together with the corresponding Laplacian eigenmaps, harmonic and geometry-aware functions, have been used in several applications, which range from surface parameterization, deformation, and compression to segmentation, clustering, and comparison. Using the linear FEM approximation of the Laplace-Beltrami operator, we derive a discrete heat kernel that is linear, stable to an irregular sampling density of the input surface, and scale covariant. With respect to previous work, this last property makes the kernel particularly suitable for shape analysis and comparison; in fact, local and global changes of the surface correspond to a re-scaling of the time parameter without affecting its spectral component. Finally, we study the scale spaces that are induced by the proposed heat kernel and exploited to provide a multi-scale approximation of scalar functions defined on 3D shapes.

We present the results of a project aimed to evaluate 2D and 3D face recognition algorithms. In particular, we focused on the potentialities of 3D-based techniques to overcome typical limitations of 2D methods in non-controlled situations. According to the reference scenario of people identification at airport check points, we built a representative database on which we tested different face recognition algorithms. We implemented and tested an improved version of a well-known state-of-the-art 3D approach, and verified that on our dataset it performs better than a widely used commercial system.

Even if today's CAD systems can easily represent free-form shapes by means of NURBS surfaces, their definition and modification still require a deep knowledge and a great skill in the manipulation of the underlying mathematical models. This paper presents an attempt to bring the feature concepts, well-known in the classical mechanical domain, to the free-form domain. The paper extends our previous work on fully free-form features to include parameterised feature templates. The free-form shapes are obtained by deformation according to specific constraint lines taking part to the feature templates definition. The feature template is adapted to the user-specified parameter values by our deformation engine, which can applied either to surfaces and curves. The method is illustrated with examples obtained with our prototype software.

The behavior of a variety of phenomena measurable on the boundary of 3D shapes is studied by modeling the set of known measurements as a scalar functionf:P → R, defined on a surface P. Furthermore, the large amount of scientific data calls for efficient techniques to correlate, describe, and analyze this data. In this context, we focus on the problem of extending the measures captured by a scalar functionf, defined on the boundary surface P of a 3D shape, to its surrounding volume. This goal is achieved by computing a sequence of volumetric functions that approximatefup to a specified accuracy and preserve its critical points. More precisely, we compute a smooth mapg: R3→ R such that the piecewise linear functionh:=gP : P → R, which interpolates the values ofgat the vertices of the triangulated surface P, is an approximation offwith the same critical points. In this way, we overcome the limitation of traditional approaches to function approximation, which are mainly based on a numerical error estimation and do not provide measurements of the topological and geometric features off. The proposed approximation scheme builds on the properties offrelated to itsglobal structure, that is, its critical points, and ignores the local details off, which can be successively introduced according to the target approximation accuracy.

Given a manifold surface {\cal M} and a continuous scalar function f:{\cal M}\rightarrow {\hbox{\rlap{I}\kern 2.0pt{\hbox{R}}}}, the Reeb graph of ({\cal M},f) is a widely used high-level descriptor of {\cal M} and its usefulness has been demonstrated for a variety of applications, which range from shape parameterization and abstraction to deformation and comparison. In this context, we propose a novel contouring algorithm for the construction of a discrete Reeb graph with a minimal number of nodes, which correspond to the critical points of f (i.e., minima, maxima, and saddle points) and its level sets passing through the saddle points. In this way, we do not need to sample, sweep, or increasingly sort the f-values. Since most of the computation uses only local information on the mesh connectivity, equipped with the f-values at the surface vertices, the proposed approach is insensitive to noise and requires a small-memory footprint and temporary data structures. Furthermore, we maintain the parametric nature of the Reeb graph with respect to the input scalar function and we efficiently extract the Reeb graph of time-varying maps. Indicating with n and s the number of vertices of {\cal M} and saddle points of f, the overall computational cost O(sn) is competitive with respect to the O(n\,\log \,n) cost of previous work. This cost becomes optimal if {\cal M} is highly sampled or s\le \log n, as it happens for Laplacian eigenfunctions, harmonic maps, and one-forms.

Given a manifold surface M and a continuous function f : M rarr R, the Reeb graph of (M, f) is a widely-used high-level descriptor of M and its usefulness has been demonstrated for a variety of applications, which range from shape parameterization and abstraction to deformation and comparison. In this context, we propose a novel computation of the Reeb graph that is based on the analysis of the iso-contours solely at saddle points and does not require sampling or sweeping the image of f. Furthermore, the proposed approach does not use global sorting steps of the function values and exploits only a local information on f, without handling it as a whole. By combining the minimal number of nodes in the Reeb graph with the use of a small amount of memory footprint and temporary data structures, the overall computation takes O(sn)-time, where n is the number of vertices of the triangulation of M and s is the number of saddles of f. Finally, the technique can be easily extended to compute the Reeb graphs of time-varying functions.

Abstract Given a 3D solid model S represented by a tetrahedral mesh, we describe a novel algorithm to compute a hierarchy of convex polyhedra that tightly enclose S. The hierarchy can be browsed at interactive speed on a modern PC and it is useful for implementing an intuitive feature selection paradigm for 3D editing environments. Convex parts often coincide with perceptually relevant shape components and, for their identification, existing methods rely on the boundary surface only. In contrast, we show that the notion of part concavity can be expressed and implemented more intuitively and efficiently by exploiting a tetrahedrization of the shape volume. The method proposed is completely automatic, and generates a tree of convex polyhedra in which the root is the convex hull of the whole shape, and the leaves are the tetrahedra of the input mesh. The algorithm proceeds bottom‐up by hierarchically clustering tetrahedra into nearly convex aggregations, and the whole process is significantly fast. We prove that, in the average case, for a mesh of n tetrahedra O(n log2n) operations are sufficient to compute the whole tree.

In the latest years, distributed virtual worlds populated by static and dynamic 3D shapes have grown significantly, and the need to model and process them effectively has become a critical issue. The introduction of semantic annotations for capturing characteristics and behaviours is foreseen as a fundamental contribution to move from traditional geometric shapes towards self-describing semantic shapes. To this aim, we describe the foundations of a novel system that allows us to perform non-trivial segmentations of 3D surface meshes and to annotate the detected parts through concepts expressed by an ontology. Each part is connected to an instance in a knowledge base, allowing easier retrieval in a semantics-based context. We show how the part-based annotation framework might be used in two scenarios, namely for the creation of avatars in emerging Internet-based virtual worlds and for product design in emanufacturing.

In this paper we propose a method for the automatic extraction and annotation of the animation control skeleton of virtual humans, which relies on an a-priori knowledge of the human anatomy. The method is based on a segmentation of the virtual human shape into semantically meaningful features, like arms or legs, and on an automatic location and labeling of joints of the control skeleton. The method is particularly relevant for computer animation where the process still largely relies on manual tasks, and especially for virtual characters built on real scanned data. Several examples will show the results obtained with our approach.

Recent advances in the parameterization and adaptive sampling of disc-like surfaces have brought a renewed interest on the global parameterization problem and, more specifically, on the cut-graph search. This paper focuses on the calculation of a family of generators and cut-graphs for the global parameterization of arbitrary triangle meshes. This result is achieved by combining the construction of harmonic scalar fields f : M rarr R of known maxima and minima with the quasi Morse-Smale complex of(M, f). The proposed technique has a simple implementation and outperforms previous work in terms of smoothness of the cut-graphs, stability with respect to the surface sampling, tessellation, topological noise (e.g., tiny handles), and capability of handling boundary components. Since we generate a family of cut-graphs, we also provide a comparison between the parameterizations of M induced by two cut-graphs.

Polygonal meshes obtained from acquisition of real-world objects may easily exhibit topological or geometrical defects, which often prevent subsequent processing and analysis to provide satisfactory results. This paper describes the foundations of ReMESH, a user-friendly graphical tool which incorporates several mesh-repairing features, and allows to perform a kind of low-level editing which is often missing in most existing software packages. We show how state-of-the-art techniques have been adapted and extended to form an intuitive and integrated environment, and introduce some optimizations and novel ideas that make ReMESH particularly efficient. The main application in which the tool proves to be extremely useful is the post-processing of scanned surface models. In this context, ReMESH represents a valid support for the production of certified quality meshes

In this paper, we describe a hierarchical face clustering algorithm for triangle meshes based on fitting primitives belonging to an arbitrary set. The method proposed is completely automatic, and generates a binary tree of clusters, each of which is fitted by one of the primitives employed. Initially, each triangle represents a single cluster; at every iteration, all the pairs of adjacent clusters are considered, and the one that can be better approximated by one of the primitives forms a new single cluster. The approximation error is evaluated using the same metric for all the primitives, so that it makes sense to choose which is the most suitable primitive to approximate the set of triangles in a cluster.Based on this approach, we have implemented a prototype that uses planes, spheres and cylinders, and have experimented that for meshes made of 100 K faces, the whole binary tree of clusters can be built in about 8 s on a standard PC.The framework described here has natural application in reverse engineering processes, but it has also been tested for surface denoising, feature recovery and character skinning.

Various acquisition, analysis, visualization, and compression approaches sample surfaces of 3D shapes in a uniform fashion without any attempt to align the samples with sharp edges or to adapt the sampling density to the surface curvature. Consequently, triangle meshes that interpolate these samples usually chamfer sharp features and exhibit a relatively large error in their vicinity. We present two new filters that improve the quality of these resampled models. EdgeSharpener restores the sharp edges by splitting the chamfer edges and forcing the new vertices to lie on intersections of planes extending the smooth surfaces incident upon these chamfers. Bender refines the resulting triangle mesh using an interpolating subdivision scheme that preserves the sharpness of the recovered sharp edges while bending their polyline approximations into smooth curves. A combined Sharpen&Bend postprocessing significantly reduces the error produced by feature-insensitive sampling processes. For example, we have observed that the mean-squared distortion introduced by the SwingWrapper remeshing-based compressor can often be reduced by 80 percent executing EdgeSharpener alone after decompression. For models with curved regions, this error may be further reduced by an additional 60 percent if we follow the EdgeSharpening phase by Bender.

Summary form only given. Shapes are expected to take a central role in the semantic Web in the next years, with high potential impact in several key areas: it has been predicted that geometry is poised to become the fourth wave of digital multimedia communication, where the first three waves were sound in the 1970s, images in the '80s, and video in the 90's. We present and promote discussions on the programme of activities of the Network of Excellence AIM@SHAPE, advanced and innovative models and tools for the development of semantic-based systems for handling, acquiring, and processing knowledge embedded in multidimensional digital objects, funded for four years by the European Commission under the 6th Framework Programme, 1ST project n/spl deg/ 506766. The scientific innovation sought by AIM@SHAPE includes methodological approaches to model digital shapes, as well as proposals of ontologies for modelling digital shapes and their semantics in key applied sectors. Technological innovation is measured against the creation of a coherent and integrated digital shape workbench (DSW) and its use as an e-science framework of tools and services for modelling, processing and interpreting digital shapes.

Fully free form deformation features (/spl delta/-F/sup 4/) have been proposed to overcome the limits of low-level manipulations of free form surfaces. They correspond to shapes obtained by deformation of a surface part according to geometric constraints. In our approach, a /spl delta/-F/sup 4/ is a result of the indirect manipulation of external forces applied to the nodes of a bar network coupled to the control polyhedron of a B-spline surface. The solution of the equation system corresponding to the constraint specifications, often under-constrained, requires the definition of an optimisation problem where an additional objective function has to be minimised. In this paper, we propose a new formulation of this optimisation problem where the proposed objective functions can be defined as a multiple combination of various local quantities. They can be related either to the geometry of the bar network (e.g. the length of a bar or the displacement of a node), or to its mechanical magnitudes (e.g. the external force applied at a node or a bar deformation energy). Different types of combinations are also proposed and classified according to the induced level of multi-minimisations. In this way, the shape of a /spl delta/-F/sup 4/ can be controlled globally, with a unique minimisation, or locally with different minimisations applied to sub-domains of the surface.

Abstract This paper describes a novel approach to the parameterization of triangle meshes representing 2‐manifolds with an arbitrary genus. A topology‐based decomposition of the shape is computed and used to segment the shape into primitives, which define a chart decomposition of the mesh. Then, each chart is parameterized using an extension of the barycentric coordinates method. The charts are all 0‐genus and can be of three types only, depending on the number of boundary components. The chart decomposition and the parameterization are used to define a shape graph where each node represents one primitive and the arcs code the adjacency relationships between the primitives. Conical and cylindrical primitives are coded together with their skeletal lines that are computed from and aligned with their parameterization. The application of the parameterization approach to remeshing guarantees that extraordinary vertices are localized only where two patches share a boundary and they are not scattered on the whole surface.

We focus on the lossy compression of manifold triangle meshes. Our SwingWrapper approach partitions the surface of an original mesh M into simply connected regions, called triangloids . From these, we generate a new mesh M ′ . Each triangle of M ′ is an approximation of a triangloid of M . By construction, the connectivity of M ′ is fairly regular and can be compressed to less than a bit per triangle using EdgeBreaker or one of the other recently developed schemes. The locations of the vertices of M ′ are compactly encoded with our new prediction technique, which uses a single correction parameter per vertex. SwingWrapper strives to reach a user-defined output file size rather than to guarantee a given error bound. For a variety of popular models, a rate of 0.4 bits/triangle yields an L 2 distortion of about 0.01% of the bounding box diagonal. The proposed solution may also be used to encode crude meshes for adaptive transmission or for controlling subdivision surfaces.

Typical methods for the triangulation of parametric surfaces use a sampling of the parameter space, and the wrong choice of parameterization can spoil a triangulation or even cause the algorithm to fail. We present a new method that uses a local tessellation primitive for almost-uniformly sampling and triangulating a surface, so that its parameterization becomes irrelevant. If sampling density or triangle shape has to be adaptive, the uniform mesh can be used either as an initial coarse mesh for a refinement process, or as a fine mesh to be reduced.

This paper addresses the designers' work and in particular the way they express an object shape through character lines. Based on this concept, a deformation feature is presented. The proposed approach includes curvilinear constraints to match the designer's requirements and techniques for the quality and accuracy of the produced model. This method is applied to B-spline surfaces coupled with a mechanical model of a bar network; geometric constraints are automatically and adaptively added to monitor and control the deformation process. A few examples show the results obtained by this deformation feature with the help of curvature maps, used to analyze the influence of the constraints and the resulting quality.

Shape understanding and modelling are complex procedures, which are the result of different specific processes. Generally, many steps in these processes may require a high computational-effort, thus making the use of parallel processing an interesting possibility. A typical example is feature recognition, a key tool towards shape understanding, which is applied to detect either local or region-wide characteristics. In this paper a survey is provided about the possibility of using parallel processing at different stages of the shape-understanding process. The parallelisation strategies will be described in details and results will be provided both for workstation networks and massively parallel machine (Cray T3D).

The aim of the paper is to propose a unified modelling paradigm for shape analysis and synthesis. It is a result of efforts made for the last few years to understand the meaning of shape and how current geometric modelling systems can represent and manipulate it. The concepts discussed in the first part are further illustrated through the description of two significant applications developed at the Institute for Applied Mathematics.

Shape is a very important way of perceiving and reasoning about the world. The authors introduce some considerations about shape representation and abstraction tools and their interaction with analysis and synthesis processes. A generic architecture for shape-based modelling is also outlined. The concepts discussed in the first part of the article are also exemplified through the description of some significant applications developed at the Istituto per la Matematica Applicata.

The use of network-based parallel computing is gaining an increasing popularity for different reasons. Its exploitation depends on the availability of simple but effective methodologies to parallelize applications, and the availability of portable and efficient communication libraries to develop parallel programs. These two items are necessary to obtain performance advantages, and to ensure software portability and reusability. In this paper we present our experience in parallelizing, in a systematic way, a class of Geographical Information Systems applications. We discuss the use of two well-known communication libraries (PVM and Linda). Performance results are also reported.

Shape-based modelling is a general approach to surface representation, which has a great importance in the specific context of the Antarctic sea floor reconstruction, where measurements can involve critical operations. Here, a method is proposed where shape-based surface reconstruction is achieved performing a geometric reasoning on the raw data to delineate a shape structure on which the final surface model can be built. Data of the Antarctic sea floor are collected by surveys carried out along parallel courses during which the depth of the sea is measured at almost regular intervals. The seabed is then represented by a set of profiles, corresponding to almost vertical cross sections. The surface reconstruction is performed in three steps. First, a shape-based simplification is carried out on the profiles, using a combination of the wavelet theory and the classical Douglas and Peucker algorithm. The second step consists of finding similarities in the morphology of adjacent profiles, which may suggest the presence of surface features, such as ridges and ravines. Finally, the deduced surface features are used to build a kind of skeleton on which the most appropriate triangulation can be constructed.

Abstract This paper discusses the relationships studied between manifold solids and r‐sets by defining an r‐set as a decomposition in two‐manifold cells. This decomposition is represented as a graph (Two‐manifold Cell Decomposition graph TCD) in which each node corresponds to a 2 manifold component of the regular set, while each arc or hyperarc defines a non‐manifold adjacency between components. The TCD model and data structure encoding it were designed in order to be compatible with a traditional boundary architecture.

A double description is proposed for the representation of a feature-based model which supports the distinction between form and functionality. This description consists of a primary representation in terms of geometric features ( geometric feature graph) and a set of feature-based representations which are created by transformations that are viewpoint specific and apply to the geometric feature graph.

A method is described for the extraction of morphological information from a terrain approximated by a Delaunay triangulation, in order to find a combinatorial simpler surface description while maintaining its basic features. Characteristic regions (i.e., regions with concave, convex, planar or saddle shape) are considered the basic descriptive elements of the surface morphology, and are defined by taking into account the type of adjacency between triangles. Adjacencies between regions define the surface characteristic lines, which are classified as ridges, ravines or generic creases, and characteristic points, which are classified as maxima, minima or saddle points. A graph-like data structure is constructed on these shape features, called the Characteristic Region Configuration Graph, which represents die surface in an effective and concise way.

This paper presents a method for extracting and representang features of a topographic surface approximated by triangular tales An algorithm as given which computes characteristic regions (a. e. regions having concave, convex or planar shape), characteristic lanes (ridges, ravines, generic creases) and characteristic points (maxima, minima, saddle points) The result as a new surface description an terms of an attributed hypergraph representation called Characteristic Region Configuration Graph, an which characteristic regions are considered the basic describers of the surface shape and correspond to the nodes of the graph, whale the arcs and hyperarcs represent the relationships between regions derived from characteristic lanes and points

The system described works in two steps. The first step starts from a boundary model of an object and identifies the generic shape features by considering only geometric and topological aspects. These features are divided into two general classes, protrusions and depressions, extracted as solid volumes, and arranged in a multilevel structure. This representation, called shape-feature object graph (SFOG), is capable of representing the recursive decomposition of an object in its main shape and the set of its form features (possibly compound). The SFOG is a hierarchical and relational boundary model represented by a graph in which the root component nodes correspond to the boundary representation of the main shape, while the other nodes correspond to the boundary representations of features; arcs between nodes define parent-child relations between components. In the second step, the identified features are classified according to the functional meaning in the application context. Thus, the hierarchical representation is reorganized by gluing and/or grouping sets of shape features which are functionally related in the context considered.>

In this paper a system for defining dimensions and tolerances is presented which deals with the geometric representation of the objects in a coherent and compact way. This model is a combination of a hierarchical boundary model to represent geometry of the object with features and a relational graph model to encode dimensions and tolerances. In this way, the proposed model can be considered a ”product model” that, besides geometric and topological information about the feature components of a solid object, also codifies information about dimensions represented by relative positron operators connected to faces which are the primitive geometric entities of the object model. The method can automatically control the validity of the geometric and topological model of the object each tame that a new tolerance node is added to the structure or a tolerance constraint already existing is modified. In this case, it also translates changes in dimensional values into corresponding changes an geometry and topology.

A new hierarchical model for solid object representation is described. This model, called a hierarchical face adjacency hypergraph (HFAH), is based on a relational description of the object boundary, called a face adjacency hypergraph (FAH), which considers faces as the primary topological entities defining the object boundary. The HFAH consists of a hierarchy of FAHs describing the decomposition of the boundary of an object into form features. In this paper the HFAH is described together with its internal encoding structure. Two basic transformations, called refinement and abstraction , are defined on the hierarchical model; these allow effective and efficient modifications of the hierarchical boundary model.

A method is presented for the automatic identification and extraction of feature information from the solid model of an object. The procedure consists of recognizing shape features, extracting those features as solid volumes and arranging them in a hierarchical structure. In this hierarchical model the main shape of the object is represented at the highest levels of abstraction, while form features are described at lower levels of specification. The system is divided into three modules: feature recognition, feature extraction and feature organization. The recognition step works on a face-based representation of solid objects, called Face Adjacency Hypergraph [1] and it takes advantage of the Kyprianou's method [12]. In the extraction phase every recognized form feature is completed with dummy entities to form a feasible object and in the organization step the completed features are arranged in a hierarchical graph, called Structured Face Adjacency Hypergraph, which is a modification of a model defined in a previous work [1].

A relational graph structure based on a boundary representation of solid objects is described. In this structure, called face adjacency graph, nodes represent object faces, whereas edges and vertices are encoded into arcs and hyperarcs. Based on the face adjacency graph, we define a set of primitive face-oriented Euler operators, and a set of macrooperators for face manipulation, which allow a compact definition and an efficient updating of solid objects. We briefly describe a hierarchical graph structure based on the face adjacency graph, which provides a representation of an object at different levels of detail. Thus it is consistent with the stepwise refinement process through which the object description is produced.

Abstract We propose a relational scheme for representing and modelling regular objects, which is based on the adjacency relations between faces and edges. In this structure, called edge‐face graph, the nodes represent the faces and the arcs the edges of the corresponding object. Other topological entities, such as vertices, loops of edges, and shells, can be obtained from this relational scheme. We give a formal description of the edge‐face graph, and the relationships between its properties and the topological entities of the object are analyzed in detail. Furthermore, a set of basic Euler operators based on the edge‐face adjacency relation is denned, which allow the incremental manipulation of boundary representations of solid objects.

Abstract Quadtrees are a class of hierarchical data structures particularly suitable for the representation of images in a compact form. In this paper a new algorithm is described which builds up the quadtree corresponding to polygonal multiply connected regions starting from their boundary representation.

This paper describes a method for constructing a surface representation model from a given set of data points.A Triangulated Irregular. Network has been chosen as data structure, thus representing the surface as a set of contiguous non -overlapping and irregurarly shaped triangular facets.The proposed method makes use of a Delaunay triangular grid adapted to non-convex domains. Using only representative subsets of the given set of points, the method allows the construction of approximating surfaces which rest within a predefined tolerance.