Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Automatic Positioning of 3D Objects in Freeform Surfaces Using Genetic Optimization

IP.com Disclosure Number: IPCOM000208570D
Original Publication Date: 2011-Jul-13
Included in the Prior Art Database: 2011-Jul-13
Document File: 5 page(s) / 350K

Publishing Venue

Siemens

Related People

Juergen Carstens: CONTACT

Abstract

The automatic placement of three dimensional (3D) objects relative to free form surfaces is an important problem in the simulation of games, modeling molecular-interactions, planning rescue operations and designing prosthetic devices. Especially the deepest possible position inside free form surfaces embedded in a three-dimensional room is interesting in that case. The problems hereby are object-object and surface-object collisions. These collisions should be avoided. A novel solution to the problem mentioned above is presented in the following. An algorithm is developed that combines the method of alternating variables and the genetic optimization. Therefore the problem can be described as follows.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 25% of the total text.

Page 01 of 5

(This page contains 01 pictures or other non-text object)

(This page contains 00 pictures or other non-text object)

Automatic Positioning of 3D Objects in Freeform Surfaces Using Genetic Optimization

Idea: Sajjad Baloch, US-Princeton, New Jersey; Tong Fang, US-Princeton, New Jersey

The automatic placement of three dimensional (3D) objects relative to free form surfaces is an important problem in the simulation of games, modeling molecular-interactions, planning rescue operations and designing prosthetic devices. Especially the deepest possible position inside free form surfaces embedded in a three-dimensional room is interesting in that case. The problems hereby are object-object and surface-object collisions. These collisions should be avoided.

A novel solution to the problem mentioned above is presented in the following. An algorithm is developed that combines the method of alternating variables and the genetic optimization. Therefore the problem can be described as follows.

Given a master surface Mm: Ω→ℝ3 and multiple slave surfaces Msi: Ω→ℝ3, (i= 1,…n), where Ω := ℝxℝ is the domain of Mj. The arising problem is to find the position and the orientation of an assembly Maof 3D object represented by their outer surfaces with regard to its starting position and orientation. Thereby the final position is the deepest possible inside Mm according to some distance function h under certain constraints. The change in this position and orientation may be captured by a single transformation matrix T representing the translation and rotation of Ma. To find the optimal position, the following cost function has to be fulfilled:

)

,

(

min

arg

* m

a

T M

TM

( (2)

)

,

(

min

:

)

,

( , b

= (3)

d

∩ (4)

According to the invention, the depth function h should be defined as a measure of how deep Ma is inside Mm. Depth is then gradually reduced from minimum depth hmin to maximum depth hmax in K steps. For each depth hK the optimal position is determined as depicted in figure 1. The procedure is repeated until no valid configuration is possible at a particular depth. The occurring problem is finding the transformation matrix T. T is defined as T:= TcThK, where ThKcorresponds to the current depth hK and Tccaptures the position and orientation with regard to hK. Therefore T is decomposed into two parts, which leads to a modular approach that drives the alternating variables optimization. In figure 2 the algorithm minimizing the cost function by alternating variables is depicted. It has to be mentioned that the optimization is only required for finding Tcfor a fixed depth.

To find the optimal position, general cost functional have to be used. Without loss of generality it might be consist that there exist two surfaces, for example an assembly surface Ma and a master surface Mm. Thereby Ma is positioned at depth hk. First, a transformation matrix Tcthat finds a collision free position of Ma' := TMa = TcThkMaunder some constrained...