HORUS Computer GmbH

WINCUT PRO v3.0

Decor Designer

CAD/CAM Software Package for the Windows NT operating system
1991-2000 by HORUS Computer GmbH

9th June 2000

HORUS Computer GmbH D-51449 Bergisch Gladbach PO Box 800210 Phone: (0049)-2202-98000-0 Fax: (0049)-2202-98000-22 Email: info@wincutpro.de
WINCUT PRO is a high performance CAD/CAM software package for designing and producing decors for the glass cutting industry. The whole spectrum of tasks from the initial input of design data to the online output of data to a glass cutting machine is covered by the package.
Creating decors using WINCUT PRO is very easy due to the user friendly interface. An online tutor assists the designer in producing a design in the minimum amount of time. Data may be imported in various formats making WINCUT PRO the ideal tool for upgrading existing systems to state of the art technology.

Features:

-Real time 3D decor design, performed directly on the surface of the glass, using the OpenGL graphics interface. -3D rendering and shading of the completed design. -Online checking of the design for machine compatibility. -Machine simulator for standard machines. -Six level hierarchical data structure. -Translation, rotation, scaling and mirroring of objects. -Editing of all design data using dialogue boxes. -Stringing of curves and lines to chained cuts. -Automatic smoothing of inter-cut steps. -Import of glass profiles. (PFL, DXF, TXT). -Import of all decors produced for Pting machines using previous HORUS software. -Creation of new designs from existing ones using drag and drop. -Undo/Redo feature to enable commands to be undone. -Export of glass profiles for use in form making. -Designs can be outputted to a plotter or printer. -Drivers for off-the-shelf robots. -Standard RS232 drivers for HORUS 27xx computers and the Kuhnke/Pting controller, including automatic machine detection. -Online switching between English German and French as the dialogue language. (Further languages will be added in the future). -Online documentation in English and German. (Further languages will be added in the future). -WINCUT PRO comes with a user friendly installation program.

Hardware Requirements:

WINCUT PRO runs on Intel based computers under the Windows NT v4.0 operating system (SP 5). Minimum Computer Requirements: CPU Pentium II or Pentium III ( 450MHz minimum) RAM 128MB 3.5" Floppy Disk 8GB Hard Disk CDROM Graphics Board with a Riva TNT-2 Graphics Accelerator ( Elsa Synergy-II, Elsa Erazor III Pro, Diamond Viper 770) 2 Serial Ports, 1 Parallel Port. 1024*Multisync Monitor (recommended 19 1280*1024).

Warranty:

HORUS Computer warrants that WINCUT PRO will perform substantially in accordance with the handbook accompanying the product for a period of 90 days from the day of receipt.

Service:

Updates to newer versions will be available on request as available.

Support Programme:

WINCUT PRO is subject to continual development and improvement. A support subscription guarantees the user the latest version of the software. Regular updates 3 to 4 times a year. A hotline and an email support facility are available to subscribers of the support programme.
Some or all of the above mentioned trade marks may have been registered by their manufacturers.

WINCUT PRO Price List

(Effective 9th June 2000)
WINCUT PRO V3.00 (Single Machine Standard Version) Price per license: 1 - 4 Licenses 5 - 9 Licenses 10-19 Licenses Support Programme (Annual Fee payable in advance) Price per license: 1 - 4 Licenses 5 - 9 Licenses 10-19 Licenses 3,995.-3,596.-3.196.-125,-800.- 19,980.- 17,980.- 15,980.--
Replacement Dongles (Defective unit returned for replacement) Unit price Consultancy and Training Daily rate ( + Expenses) All prices FOB + VAT
Note: Dongles should be insured to the full value of the of the software license charge. Lost or stolen dongles will be replaced for the full new price of the software only.

Real-Time Continuous Levels-of-Detail Terrain Rendering with Nested Splitting Space

Introductory FAQ

1. What is this anyway?
This is a new algorithm for real-time continuous Levels of Detail (LOD) rendering of terrain. +Results obtained from the prototype implementation prove excellent, and rival existing methods in terms of performance, visual quality, memory requirement and scalability for past and future graphics hardware.

Algorithm

1. Basics
The triangulation process is based on generating packs of triangle fans for nodes in a restricted quadtree. +Subdivide the quadtree node into four children nodes if it is not of sufficient detail level. +Adjacent nodes have a level difference of one or zero. +No elaboration, as it's not too fancy or brand new. (Covered in several existing literatures) +However, I also present a novel extension to this scheme (covered in section 4), which enable the algorithm to provide virtually unlimited scalability for past and future graphics hardware.

2. Where can it be used?

Geographic Information Systems (GIS). +Flight simulation. +Computer game with vast 3D outdoor scenes. +Military tactic training. +Basically anywhere you want immersive outdoor virtual reality world!
2. Nested Splitting Space
The really difficult part is LOD selection! Restricted quadtree only provides a "framework". +Which quadtree nodes are to be split? +Which vertices are to be included in the final triangulation? +How to ensure that the selected (enabled) vertices do fit together into a continuous mesh. +To solve this, I present the concept of Nested Splitting Space (NSS). +For each vertex, the collection of viewpoints that cause the vertex to be enabled makes up its NSS. +I use a sphere squashed to half its size in vertical direction. +Screen space error can be approximated with: E= elmax(sx, sy). +Substitute E with Em, and transform to get: l= eEmmax(sx, sy). +I use this l as the radius of the NSS. If the viewpoint is inside the ellipsoid NSS, the corresponding vertex is enabled; otherwise it's disabled. This provides fast computing and excellent visual quality control. +About LOD selection and ensuring mesh continuity with NSS: +For a quadtree node, whether or not we should split it and create its four children maps on to the NSS of its center vertex, and hence, the "splitting space". +We enlarge the NSSes according to vertex dependency during preprocessing, i.e. the ellipsoid on the vertex dependency hierarchy are nested, and hence the "nested". +The real beauty of NSS lies in its simplicity: After preprocessing, we can forget about fixing cracks during runtime, as mesh continuity is automatically preserved.
3. What's LOD and why do we need it?
Terrain has huge geometry complexity. A 2,000 2,000 heightfield 8M triangles. +And that hampers real-time visualization! (The Killer nVidia GeForce3 boasts a peak triangle rate of 100M TPS, or 3.3M triangles at 30 FPS, and aren't you going to leave room for buildings, tanks and characters?) +End of the world? Not yet! +Typical terrain models have rough and flat neighborhoods. +And dont forget the Perspective nature of 3D to 2D projection. +Efficient LOD schemes exploit these and provide different tessellation levels for different parts of the terrain. +Cut down the overall polygon number, while preserving visual quality.
Performance: +60K triangles at 30 FPS1.8 M TPS. +Even the D3D8 "Optimized Mesh" Sample (no texture/color, renders the same optimized mesh again and again) was only able to get 1.93 M TPS on the same system. +The time required for performing view-frustum culling, quadtree nodes evaluating, splitting and merging is tiny compared to that of rendering the mesh. +Visual quality: Excellent. See for yourself. +About NSS: +Abstract everything (LOD, continuity, morphing, etc.) down to a simple check and interpolating. +A simple, yet novel, solution to LOD. +About frame coherence optimization: +Distance hash table based lazy LOD evaluation gives much of the speed. +In most cases, the number of quadtree nodes evaluated is merely a small fraction of the total number of quadtree nodes in the hierarchy, with a typical ratio of 1:15. +Disabling it chops the frame rates by more than half. +About LOD accuracy adjustment: +Enables high triangle rates to be reached. +All figures mentioned afore are obtained when the implementation performs one step of subdivision. When I turned off subdivision, the portion of time spent doing CPU works increases.

Triangulation using NSS

3. Algorithm Framework
Frame Coherence Optimization During interactive visualization, the user typically moves across the terrain in a continuous fashion. +So, the difference between triangulations of subsequent frames can be fairly small compared to the size of the whole triangulation. I update the existing mesh instead of rebuilding a new one, and this can gain extra performance. +I maintain two hash tables to schedule lazy evaluation based on the maximum reevaluation distance, which is determined by viewpoint-to-NSS boundary distance.
View frustum culling Splitting quadtree nodes Merging quadtree nodes Rendering
With 6.13% 0.184% 0.245% 86.7%
Without 11.1% 3.02% 3.89% 73.4%
4. What are the difficulties faced by terrain LOD algorithms?
LOD selection: determine which parts of the terrain need a higher tessellation level and which do not. +Ensure mesh continuity: Fix cracks at the boundaries of differently sized triangles. This is a major Headache! +Vertex morphing: Hide triangulation changes to provide a stable visual image. +Hardware concerns: Performance, memory requirement, scalability, etc. +And many more +All of these require nifty algorithms and data structures. +Fitting all of the above together is the most difficult.
Performing subdivisions of more than one step will further reduce the time portion spent on the CPU side. +A unique answer to the problem of scalability.

Related Work

Investigated a wealth of related literatures: Lindstorm's, ROAM, Rttger's, Jonathon Blow's, multiresolution TIN, RTIN, PM, Geo-Mipmap, and so on. +In theory: Please see the paper for a detailed "Related Work" section. +In practice: Let's compare with the Geo-Mipmap. +Cited as specially designed to "push as much triangles through the pipeline as the hardware can handle, and with the least amount of CPU overhead". +Results: 11K triangles at 50 FPS (which is 0.55 M TPS) on a slightly inferior machine (Pentium II 434, Viper 550). +Far behind the 1.8 M TPS I have reached.
Vertex Morphing The terrain is triangulated dynamically, and as the viewer moves, the underlying meshes changes. +As a vertex is enabled or disabled, it jumped to its new position instantly, causing an effect called "vertex pop". With a long popping, this side effect becomes noticeable, unstablizing visual quality. +To hide this, I incorporate a "buffering" distance into each NSS radius and test use the new radii. Morphing occurs when the vertex is caught between the old NSS boundary and new boundary. I use the viewpoint-to-boundary distance to interpolate between old and new position, result in the vertex gradually slides to its new position. +This vertex morphing mechanism is versatile, with freely adjustable morphing distance, and requires zero memory overheads.

5. What can I expect from the algorithm presented in this project?
Short answer: Look at the accompanying pictures at the right section of this board (rendered on an average PC at >40 frames per second) and the running DEMO. Seeing is believing. +Long answer: hey, that's what the Discussion/Comparison/Conclusion sections are for!
Vertex morphing by incorporating a buffer distance into NSS
LOD Accuracy Adjustment Newest generation of GPU render triangles faster than CPUs can keep up with fine-grained LOD evaluation, resulting in a "hungry" GPU or an "exhausted" CPU. +I provide a novel solution to this: LOD accuracy adjustment. (An extension to ordinary continuous LOD triangulation). With the help of this, we can: +Send more triangles using the same amount of CPU time! +Send the same number of triangles using less CPU time! +How? Observe a triangulation, I found that if I subdivide all triangles in the mesh into four smaller one, continuity is still maintained. +Subdivide once and get a 4 mesh, twice to get a 16 mesh, thrice to get a 64 mesh! +Just dump the triangles at that starving GPU. This time, the triangulation is not optimal, but the raw horsepower of today's graphics hardware overcome this easily, and less CPU work is needed. +Fit into our NSS methodology beautifully: the new vertices just use the NSS of those vertices who, after subdivision, cause them to be created. Don't worry about vertex morphing, etc.

Conclusion

1. Contributions
The new concept of NSS is presented, which provides an elegant solution for tackling all sorts of problems faced by LOD algorithms. This is utilizable by other LOD algorithms. +An advanced terrain LOD algorithm using distance based hash tables to drive the refining and coarsening process is developed. Combined with our novel LOD accuracy adjustment feature, the scheme provides high performance and excellent visual quality, rivaling existing algorithms.
Dynamic Mesh Resolution Fine-Tuning, Procedural Details Accommodation, and Many More Oops, no more room left! +Please see the paper for more detailed information on these topics.
LOD accuracy adjustment by subdivision

2. Future work

Adoption of NSS to arbitrary mesh topology. +Incorporation of subdivision surface to provide smooth LOD for skinned character. +And many more

Results and Discussion

Prototype implementation: The running DEMO. +Testing environment: +Single Pentium III 500mhz machine. +An ELSA Erazor III Pro (TNT2 Pro) 3D accelerator with 32M onboard VRAM, AGP2. +1024768 viewport, 16bit color buffer and 16bit depth buffer. +Simulating a flight over a 20492049 heightfield.
View-frustum culling Merging quadtree nodes Splitting quadtree nodes Morphing (optional) Rendering mesh Total
Time 2 ms 0.06 ms 0.08 ms 2.2 ms 28.3 ms 32.64 ms
Percentage 6.13% 0.184% 0.245% 6.74% 86.7% 100%
Sample frames generated by the prototype implementation, with and without wire-frame shown.