Keywords: octrees, volume-oriented geometric modelling, consistency checks,.

This paper presents a volume-oriented approach for geometric modelling based on octrees generated by intersections of half-spaces. Our method leads to fast and efficient algorithms regarding runtime, memory requirements, and file size. Encoding these octrees as binary streams makes them suitable to get multiplexed with other octree-encoded objects. It is shown that by integrating all generation and encoding steps into one single pass no redundant work has to be done, and thus, even a generation on-the-fly is possible, useful in various applications like collision detection and global consistency in case of cooperative work.

By choosing a special, normalised plane equation for each half-space the necessary costs for determining whether or not a cell needs to be refined can be reduced to a floating point comparison of one of the plane's parameters, instead of calculating this explicitly like in conventional agorithms. Boolean operators - intersection, union, and difference - applied to these octree-encoded half-spaces allow to generate all kind of objects - convex and non-convex - while the latter ones have to be built as unions from convex components. Under retention of a certain processing order - given by a disjunctive normal form - the overall costs when processing all half-spaces in one pass can be reduced to a minimum, free of any redundant refinements, and directly proportional to the surface of the resulting object.

Encoding the octrees as binary streams is equivalent to a linearisation - like a depth-first search - where all nodes and leafs of the tree are processed and written down in a predescribed manner. For handling binary streams and for multiplexing two or more of them stacks are necessary, providing also the position number for the actual processed node or leaf during the entire process [1]. Two possible applications of multiplexed binary streams are collision detection and global consistency in a cooperative working environment--both discussed in the paper. While the first one checks for unintentionally intersections or gaps between parts of the model - due to mistakes during the modelling phase and round-off errors when storing the model to a file - the latter one identifies any conflicts regarding the model whenever an engineer wants to write back his modified parts of the model to the entire model. Structural analysis is another application that can be organised via our octree structure in an elegant way. For that, an intermediate connection model [2] for creating a three dimensional hexahedral finite element mesh has to be derived.

With the octree toolbox presented in this paper, we expect that the computer support and the degree of automatisation of planning processes in civil engineering, from the early architectural modelling up to all kind of simulation tasks, can be significantly improved.

1

A. Frank, "Organisationsprinzipien zur Integration von geometrischer Modellierung, numerischer Simulation und Visualisierung", PhD thesis, Department of Computer Science, TU München, 2000.

2

C. v. Treeck, R. Romberg, and E. Rank, "Simulation based on the product model standard IFC", submitted to: Building Simulation 2003, Eindhoven, Netherlands.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £123 +P&P)