Sparkling Water (H2O) Machine Learning
Overview
The rsparkling extension package provides bindings to H2O’s distributed machine learning algorithms via sparklyr. In particular, rsparkling allows you to access the machine learning routines provided by the Sparkling Water Spark package.
Together with sparklyr’s dplyr interface, you can easily create and tune H2O machine learning workflows on Spark, orchestrated entirely within R.
rsparkling provides a few simple conversion functions that allow the user to transfer data between Spark DataFrames and H2O Frames. Once the Spark DataFrames are available as H2O Frames, the h2o R interface can be used to train H2O machine learning algorithms on the data.
A typical machine learning pipeline with rsparkling might be composed of the following stages. To fit a model, you might need to:
- Perform SQL queries through the sparklyr dplyr interface,
- Use the
sdf_*
andft_*
family of functions to generate new columns, or partition your data set, - Convert your training, validation and/or test data frames into H2O Frames using the
as_h2o_frame
function, - Choose an appropriate H2O machine learning algorithm to model your data,
- Inspect the quality of your model fit, and use it to make predictions with new data.
Installation
You can install the rsparkling package from CRAN as follows:
install.packages("rsparkling")
Then set the Sparkling Water version for rsparkling.:
options(rsparkling.sparklingwater.version = "2.1.14")
For Spark 2.0.x
set rsparkling.sparklingwater.version
to 2.0.3
instead, for Spark 1.6.2
use 1.6.8
.
Using H2O
Now let’s walk through a simple example to demonstrate the use of H2O’s machine learning algorithms within R. We’ll use h2o.glm to fit a linear regression model. Using the built-in mtcars
dataset, we’ll try to predict a car’s fuel consumption (mpg
) based on its weight (wt
), and the number of cylinders the engine contains (cyl
).
First, we will initialize a local Spark connection, and copy the mtcars
dataset into Spark.
library(rsparkling)
library(sparklyr)
library(h2o)
library(dplyr)
sc <- spark_connect("local", version = "2.1.0")
mtcars_tbl <- copy_to(sc, mtcars, "mtcars")
Now, let’s perform some simple transformations – we’ll
- Remove all cars with horsepower less than 100,
- Produce a column encoding whether a car has 8 cylinders or not,
- Partition the data into separate training and test data sets,
- Fit a model to our training data set,
- Evaluate our predictive performance on our test dataset.
# transform our data set, and then partition into 'training', 'test'
partitions <- mtcars_tbl %>%
filter(hp >= 100) %>%
mutate(cyl8 = cyl == 8) %>%
sdf_partition(training = 0.5, test = 0.5, seed = 1099)
Now, we convert our training and test sets into H2O Frames using rsparkling conversion functions. We have already split the data into training and test frames using dplyr.
training <- as_h2o_frame(sc, partitions$training, strict_version_check = FALSE)
test <- as_h2o_frame(sc, partitions$test, strict_version_check = FALSE)
Alternatively, we can use the h2o.splitFrame()
function instead of sdf_partition()
to partition the data within H2O instead of Spark (e.g. partitions <- h2o.splitFrame(as_h2o_frame(mtcars_tbl), 0.5)
)
# fit a linear model to the training dataset
glm_model <- h2o.glm(x = c("wt", "cyl"),
y = "mpg",
training_frame = training,
lambda_search = TRUE)
For linear regression models produced by H2O, we can use either print()
or summary()
to learn a bit more about the quality of our fit. The summary()
method returns some extra information about scoring history and variable importance.
glm_model
## Model Details:
## ==============
##
## H2ORegressionModel: glm
## Model ID: GLM_model_R_1510348062048_1
## GLM Model: summary
## family link regularization
## 1 gaussian identity Elastic Net (alpha = 0.5, lambda = 0.05468 )
## lambda_search
## 1 nlambda = 100, lambda.max = 5.4682, lambda.min = 0.05468, lambda.1se = -1.0
## number_of_predictors_total number_of_active_predictors
## 1 2 2
## number_of_iterations training_frame
## 1 100 frame_rdd_32_929e407384e0082416acd4c9897144a0
##
## Coefficients: glm coefficients
## names coefficients standardized_coefficients
## 1 Intercept 32.997281 16.625000
## 2 cyl -0.906688 -1.349195
## 3 wt -2.712562 -2.282649
##
## H2ORegressionMetrics: glm
## ** Reported on training data. **
##
## MSE: 2.03293
## RMSE: 1.425808
## MAE: 1.306314
## RMSLE: 0.08238032
## Mean Residual Deviance : 2.03293
## R^2 : 0.8265696
## Null Deviance :93.775
## Null D.o.F. :7
## Residual Deviance :16.26344
## Residual D.o.F. :5
## AIC :36.37884
The output suggests that our model is a fairly good fit, and that both a cars weight, as well as the number of cylinders in its engine, will be powerful predictors of its average fuel consumption. (The model suggests that, on average, heavier cars consume more fuel.)
Let’s use our H2O model fit to predict the average fuel consumption on our test data set, and compare the predicted response with the true measured fuel consumption. We’ll build a simple ggplot2 plot that will allow us to inspect the quality of our predictions.
library(ggplot2)
# compute predicted values on our test dataset
pred <- h2o.predict(glm_model, newdata = test)
# convert from H2O Frame to Spark DataFrame
predicted <- as_spark_dataframe(sc, pred, strict_version_check = FALSE)
# extract the true 'mpg' values from our test dataset
actual <- partitions$test %>%
select(mpg) %>%
collect() %>%
`[[`("mpg")
# produce a data.frame housing our predicted + actual 'mpg' values
data <- data.frame(
predicted = predicted,
actual = actual
)
# a bug in data.frame does not set colnames properly; reset here
names(data) <- c("predicted", "actual")
# plot predicted vs. actual values
ggplot(data, aes(x = actual, y = predicted)) +
geom_abline(lty = "dashed", col = "red") +
geom_point() +
theme(plot.title = element_text(hjust = 0.5)) +
coord_fixed(ratio = 1) +
labs(
x = "Actual Fuel Consumption",
y = "Predicted Fuel Consumption",
title = "Predicted vs. Actual Fuel Consumption"
)
Although simple, our model appears to do a fairly good job of predicting a car’s average fuel consumption.
As you can see, we can easily and effectively combine dplyr data transformation pipelines with the machine learning algorithms provided by H2O’s Sparkling Water.
Algorithms
Once the H2OContext
is made available to Spark (as demonstrated below), all of the functions in the standard h2o R interface can be used with H2O Frames (converted from Spark DataFrames). Here is a table of the available algorithms:
| Function | Description |
|---|---|
h2o.glm |
Generalized Linear Model |
h2o.deeplearning |
Multilayer Perceptron |
h2o.randomForest |
Random Forest |
h2o.gbm |
Gradient Boosting Machine |
h2o.naiveBayes |
Naive-Bayes |
h2o.prcomp |
Principal Components Analysis |
h2o.svd |
Singular Value Decomposition |
h2o.glrm |
Generalized Low Rank Model |
h2o.kmeans |
K-Means Clustering |
h2o.anomaly |
Anomaly Detection via Deep Learning Autoencoder |
Additionally, the h2oEnsemble R package can be used to generate Super Learner ensembles of H2O algorithms:
| Function | Description |
|---|---|
h2o.ensemble |
Super Learner / Stacking |
h2o.stack |
Super Learner / Stacking |
Transformers
A model is often fit not on a dataset as-is, but instead on some transformation of that dataset. Spark provides feature transformers, facilitating many common transformations of data within a Spark DataFrame, and sparklyr exposes these within the ft_*
family of functions. Transformers can be used on Spark DataFrames, and the final training set can be sent to the H2O cluster for machine learning.
| Function | Description |
|---|---|
ft_binarizer
|
Threshold numerical features to binary (0/1) feature |
ft_bucketizer
|
Bucketizer transforms a column of continuous features to a column of feature buckets |
ft_discrete_cosine_transform
|
Transforms a length NN real-valued sequence in the time domain into another length NN real-valued sequence in the frequency domain |
ft_elementwise_product
|
Multiplies each input vector by a provided weight vector, using element-wise multiplication. |
ft_index_to_string
|
Maps a column of label indices back to a column containing the original labels as strings |
ft_quantile_discretizer
|
Takes a column with continuous features and outputs a column with binned categorical features |
ft_sql_transformer
|
Implements the transformations which are defined by a SQL statement |
ft_string_indexer
|
Encodes a string column of labels to a column of label indices |
ft_vector_assembler
|
Combines a given list of columns into a single vector column |
Examples
We will use the iris
data set to examine a handful of learning algorithms and transformers. The iris data set measures attributes for 150 flowers in 3 different species of iris.
iris_tbl <- copy_to(sc, iris, "iris", overwrite = TRUE)
iris_tbl
## # Source: table<iris> [?? x 5]
## # Database: spark_connection
## Sepal_Length Sepal_Width Petal_Length Petal_Width Species
## <dbl> <dbl> <dbl> <dbl> <chr>
## 1 5.1 3.5 1.4 0.2 setosa
## 2 4.9 3.0 1.4 0.2 setosa
## 3 4.7 3.2 1.3 0.2 setosa
## 4 4.6 3.1 1.5 0.2 setosa
## 5 5.0 3.6 1.4 0.2 setosa
## 6 5.4 3.9 1.7 0.4 setosa
## 7 4.6 3.4 1.4 0.3 setosa
## 8 5.0 3.4 1.5 0.2 setosa
## 9 4.4 2.9 1.4 0.2 setosa
## 10 4.9 3.1 1.5 0.1 setosa
## # ... with more rows
Convert to an H2O Frame:
iris_hf <- as_h2o_frame(sc, iris_tbl, strict_version_check = FALSE)
K-Means Clustering
Use H2O’s K-means clustering to partition a dataset into groups. K-means clustering partitions points into k
groups, such that the sum of squares from points to the assigned cluster centers is minimized.
kmeans_model <- h2o.kmeans(training_frame = iris_hf,
x = 3:4,
k = 3,
seed = 1)
To look at particular metrics of the K-means model, we can use h2o.centroid_stats()
and h2o.centers()
or simply print out all the model metrics using print(kmeans_model)
.
# print the cluster centers
h2o.centers(kmeans_model)
## petal_length petal_width
## 1 1.462000 0.24600
## 2 5.566667 2.05625
## 3 4.296154 1.32500
# print the centroid statistics
h2o.centroid_stats(kmeans_model)
## Centroid Statistics:
## centroid size within_cluster_sum_of_squares
## 1 1 50.00000 1.41087
## 2 2 48.00000 9.29317
## 3 3 52.00000 7.20274
PCA
Use H2O’s Principal Components Analysis (PCA) to perform dimensionality reduction. PCA is a statistical method to find a rotation such that the first coordinate has the largest variance possible, and each succeeding coordinate in turn has the largest variance possible.
pca_model <- h2o.prcomp(training_frame = iris_hf,
x = 1:4,
k = 4,
seed = 1)
## Warning in doTryCatch(return(expr), name, parentenv, handler): _train:
## Dataset used may contain fewer number of rows due to removal of rows with
## NA/missing values. If this is not desirable, set impute_missing argument in
## pca call to TRUE/True/true/... depending on the client language.
pca_model
## Model Details:
## ==============
##
## H2ODimReductionModel: pca
## Model ID: PCA_model_R_1510348062048_3
## Importance of components:
## pc1 pc2 pc3 pc4
## Standard deviation 7.861342 1.455041 0.283531 0.154411
## Proportion of Variance 0.965303 0.033069 0.001256 0.000372
## Cumulative Proportion 0.965303 0.998372 0.999628 1.000000
##
##
## H2ODimReductionMetrics: pca
##
## No model metrics available for PCA
Random Forest
Use H2O’s Random Forest to perform regression or classification on a dataset. We will continue to use the iris dataset as an example for this problem.
As usual, we define the response and predictor variables using the x
and y
arguments. Since we’d like to do a classification, we need to ensure that the response column is encoded as a factor (enum) column.
y <- "Species"
x <- setdiff(names(iris_hf), y)
iris_hf[,y] <- as.factor(iris_hf[,y])
We can split the iris_hf
H2O Frame into a train and test set (the split defaults to 75⁄25 train/test).
splits <- h2o.splitFrame(iris_hf, seed = 1)
Then we can train a Random Forest model:
rf_model <- h2o.randomForest(x = x,
y = y,
training_frame = splits[[1]],
validation_frame = splits[[2]],
nbins = 32,
max_depth = 5,
ntrees = 20,
seed = 1)
Since we passed a validation frame, the validation metrics will be calculated. We can retrieve individual metrics using functions such as h2o.mse(rf_model, valid = TRUE)
. The confusion matrix can be printed using the following:
h2o.confusionMatrix(rf_model, valid = TRUE)
## Confusion Matrix: Row labels: Actual class; Column labels: Predicted class
## setosa versicolor virginica Error Rate
## setosa 7 0 0 0.0000 = 0 / 7
## versicolor 0 13 0 0.0000 = 0 / 13
## virginica 0 1 10 0.0909 = 1 / 11
## Totals 7 14 10 0.0323 = 1 / 31
To view the variable importance computed from an H2O model, you can use either the h2o.varimp()
or h2o.varimp_plot()
functions:
h2o.varimp_plot(rf_model)
Gradient Boosting Machine
The Gradient Boosting Machine (GBM) is one of H2O’s most popular algorithms, as it works well on many types of data. We will continue to use the iris dataset as an example for this problem.
Using the same dataset and x
and y
from above, we can train a GBM:
gbm_model <- h2o.gbm(x = x,
y = y,
training_frame = splits[[1]],
validation_frame = splits[[2]],
ntrees = 20,
max_depth = 3,
learn_rate = 0.01,
col_sample_rate = 0.7,
seed = 1)
Since this is a multi-class problem, we may be interested in inspecting the confusion matrix on a hold-out set. Since we passed along a validatin_frame
at train time, the validation metrics are already computed and we just need to retreive them from the model object.
h2o.confusionMatrix(gbm_model, valid = TRUE)
## Confusion Matrix: Row labels: Actual class; Column labels: Predicted class
## setosa versicolor virginica Error Rate
## setosa 7 0 0 0.0000 = 0 / 7
## versicolor 0 13 0 0.0000 = 0 / 13
## virginica 0 1 10 0.0909 = 1 / 11
## Totals 7 14 10 0.0323 = 1 / 31
Deep Learning
Use H2O’s Deep Learning to perform regression or classification on a dataset, extact non-linear features generated by the deep neural network, and/or detect anomalies using a deep learning model with auto-encoding.
In this example, we will use the prostate
dataset available within the h2o package:
path <- system.file("extdata", "prostate.csv", package = "h2o")
prostate_df <- spark_read_csv(sc, "prostate", path)
head(prostate_df)
## # Source: lazy query [?? x 9]
## # Database: spark_connection
## ID CAPSULE AGE RACE DPROS DCAPS PSA VOL GLEASON
## <int> <int> <int> <int> <int> <int> <dbl> <dbl> <int>
## 1 1 0 65 1 2 1 1.4 0.0 6
## 2 2 0 72 1 3 2 6.7 0.0 7
## 3 3 0 70 1 1 2 4.9 0.0 6
## 4 4 0 76 2 2 1 51.2 20.0 7
## 5 5 0 69 1 1 1 12.3 55.9 6
## 6 6 1 71 1 3 2 3.3 0.0 8
Once we’ve done whatever data manipulation is required to run our model we’ll get a reference to it as an h2o frame then split it into training and test sets using the h2o.splitFrame
function:
prostate_hf <- as_h2o_frame(sc, prostate_df, strict_version_check = FALSE)
splits <- h2o.splitFrame(prostate_hf, seed = 1)
Next we define the response and predictor columns.
y <- "VOL"
#remove response and ID cols
x <- setdiff(names(prostate_hf), c("ID", y))
Now we can train a deep neural net.
dl_fit <- h2o.deeplearning(x = x, y = y,
training_frame = splits[[1]],
epochs = 15,
activation = "Rectifier",
hidden = c(10, 5, 10),
input_dropout_ratio = 0.7)
Evaluate performance on a test set:
h2o.performance(dl_fit, newdata = splits[[2]])
## H2ORegressionMetrics: deeplearning
##
## MSE: 253.7022
## RMSE: 15.92803
## MAE: 12.90077
## RMSLE: 1.885052
## Mean Residual Deviance : 253.7022
Note that the above metrics are not reproducible when H2O’s Deep Learning is run on multiple cores, however, the metrics should be fairly stable across repeat runs.
Grid Search
H2O’s grid search capabilities currently supports traditional (Cartesian) grid search and random grid search. Grid search in R provides the following capabilities:
H2OGrid
class: Represents the results of the grid searchh2o.getGrid(<grid_id>, sort_by, decreasing)
: Display the specified gridh2o.grid
: Start a new grid search parameterized by- model builder name (e.g.,
algorithm = "gbm"
) - model parameters (e.g.,
ntrees = 100
) hyper_parameters
: attribute for passing a list of hyper parameters (e.g.,list(ntrees=c(1,100), learn_rate=c(0.1,0.001))
)search_criteria
: optional attribute for specifying more a advanced search strategy
- model builder name (e.g.,
Cartesian Grid Search
By default, h2o.grid()
will train a Cartesian grid search – meaning, all possible models in the specified grid. In this example, we will re-use the prostate data as an example dataset for a regression problem.
splits <- h2o.splitFrame(prostate_hf, seed = 1)
y <- "VOL"
#remove response and ID cols
x <- setdiff(names(prostate_hf), c("ID", y))
After prepping the data, we define a grid and execute the grid search.
# GBM hyperparamters
gbm_params1 <- list(learn_rate = c(0.01, 0.1),
max_depth = c(3, 5, 9),
sample_rate = c(0.8, 1.0),
col_sample_rate = c(0.2, 0.5, 1.0))
# Train and validate a grid of GBMs
gbm_grid1 <- h2o.grid("gbm", x = x, y = y,
grid_id = "gbm_grid1",
training_frame = splits[[1]],
validation_frame = splits[[1]],
ntrees = 100,
seed = 1,
hyper_params = gbm_params1)
# Get the grid results, sorted by validation MSE
gbm_gridperf1 <- h2o.getGrid(grid_id = "gbm_grid1",
sort_by = "mse",
decreasing = FALSE)
gbm_gridperf1
## H2O Grid Details
## ================
##
## Grid ID: gbm_grid1
## Used hyper parameters:
## - col_sample_rate
## - learn_rate
## - max_depth
## - sample_rate
## Number of models: 36
## Number of failed models: 0
##
## Hyper-Parameter Search Summary: ordered by increasing mse
## col_sample_rate learn_rate max_depth sample_rate model_ids
## 1 1.0 0.1 9 1.0 gbm_grid1_model_35
## 2 0.5 0.1 9 1.0 gbm_grid1_model_34
## 3 1.0 0.1 9 0.8 gbm_grid1_model_17
## 4 0.5 0.1 9 0.8 gbm_grid1_model_16
## 5 1.0 0.1 5 0.8 gbm_grid1_model_11
## mse
## 1 88.10947523138782
## 2<PHONE_NUMBER>994892
## 3<PHONE_NUMBER>1923726
## 4<PHONE_NUMBER>351778
## 5<PHONE_NUMBER>109763
##
## ---
## col_sample_rate learn_rate max_depth sample_rate model_ids
## 31 0.5 0.01 3 0.8 gbm_grid1_model_1
## 32 0.2 0.01 5 1.0 gbm_grid1_model_24
## 33 0.5 0.01 3 1.0 gbm_grid1_model_19
## 34 0.2 0.01 5 0.8 gbm_grid1_model_6
## 35 0.2 0.01 3 1.0 gbm_grid1_model_18
## 36 0.2 0.01 3 0.8 gbm_grid1_model_0
## mse
## 31<PHONE_NUMBER>723162
## 32<PHONE_NUMBER>5687294
## 33<PHONE_NUMBER>3785045
## 34<PHONE_NUMBER>5305735
## 35<PHONE_NUMBER>6919456
## 36<PHONE_NUMBER>617712
Random Grid Search
H2O’s Random Grid Search samples from the given parameter space until a set of constraints is met. The user can specify the total number of desired models using (e.g. max_models = 40
), the amount of time (e.g. max_runtime_secs = 1000
), or tell the grid to stop after performance stops improving by a specified amount. Random Grid Search is a practical way to arrive at a good model without too much effort.
The example below is set to run fairly quickly – increase max_runtime_secs
or max_models
to cover more of the hyperparameter space in your grid search. Also, you can expand the hyperparameter space of each of the algorithms by modifying the definition of hyper_param
below.
# GBM hyperparamters
gbm_params2 <- list(learn_rate = seq(0.01, 0.1, 0.01),
max_depth = seq(2, 10, 1),
sample_rate = seq(0.5, 1.0, 0.1),
col_sample_rate = seq(0.1, 1.0, 0.1))
search_criteria2 <- list(strategy = "RandomDiscrete",
max_models = 50)
# Train and validate a grid of GBMs
gbm_grid2 <- h2o.grid("gbm", x = x, y = y,
grid_id = "gbm_grid2",
training_frame = splits[[1]],
validation_frame = splits[[2]],
ntrees = 100,
seed = 1,
hyper_params = gbm_params2,
search_criteria = search_criteria2)
# Get the grid results, sorted by validation MSE
gbm_gridperf2 <- h2o.getGrid(grid_id = "gbm_grid2",
sort_by = "mse",
decreasing = FALSE)
To get the best model, as measured by validation MSE, we simply grab the first row of the gbm_gridperf2@summary_table
object, since this table is already sorted such that the lowest MSE model is on top.
gbm_gridperf2@summary_table[1,]
## Hyper-Parameter Search Summary: ordered by increasing mse
## col_sample_rate learn_rate max_depth sample_rate model_ids
## 1 0.8 0.01 2 0.7 gbm_grid2_model_35
## mse
## 1<PHONE_NUMBER>1586288
In the examples above, we generated two different grids, specified by grid_id
. The first grid was called grid_id = "gbm_grid1"
and the second was called grid_id = "gbm_grid2"
. However, if we are using the same dataset & algorithm in two grid searches, it probably makes more sense just to add the results of the second grid search to the first. If you want to add models to an existing grid, rather than create a new one, you simply re-use the same grid_id
.
Exporting Models
There are two ways of exporting models from H2O – saving models as a binary file, or saving models as pure Java code.
Binary Models
The more traditional method is to save a binary model file to disk using the h2o.saveModel()
function. To load the models using h2o.loadModel()
, the same version of H2O that generated the models is required. This method is commonly used when H2O is being used in a non-production setting.
A binary model can be saved as follows:
h2o.saveModel(my_model, path = "/Users/me/h2omodels")
Java (POJO) Models
One of the most valuable features of H2O is it’s ability to export models as pure Java code, or rather, a “Plain Old Java Object” (POJO). You can learn more about H2O POJO models in this POJO quickstart guide. The POJO method is used most commonly when a model is deployed in a production setting. POJO models are ideal for when you need very fast prediction response times, and minimal requirements – the POJO is a standalone Java class with no dependencies on the full H2O stack.
To generate the POJO for your model, use the following command:
h2o.download_pojo(my_model, path = "/Users/me/h2omodels")
Finally, disconnect with:
spark_disconnect_all()
## [1] 1
You can learn more about how to take H2O models to production in the productionizing H2O models section of the H2O docs.
Additional Resources
If you are new to H2O for machine learning, we recommend you start with the Intro to H2O Tutorial, followed by the H2O Grid Search & Model Selection Tutorial. There are a number of other H2O R tutorials and demos available, as well as the H2O World 2015 Training Gitbook, and the Machine Learning with R and H2O Booklet (pdf).


Three New 6 Bedroom Vacation Home. Enjoy a family reunion home for your next vacation in Minnesota. Only Saturday to Saturday Weekly Reservations are taken between June 11-August 20, 2016 for all Home Rentals: Home 1, 2, 3, 4, 7A, 10, 11 and 12.
Congratulations, you have discovered a Northern Minnesota family resort paradise established in the 1930's! White Birch Resort is the perfect place for your next family resort vacation! This great resort sits on the northeast corner of beautiful Blackduck Lake which consists of 2,596 acres. With it's natural beauty of overwhelming sunsets, calm summer lake breezes and spectacular views you are sure to receive the best resort lake view on Blackduck Lake. Even though Blackduck Lake is known as a Premier Northern Minnesota walleye fishing lake and has been rated on the top "BEST" Minnesota walleye opener lakes in the state, you can also catch northern pike, perch, bass, sunfish, crappie, and drum fish at this Blackduck MN resort.
White Birch Resort has ten beautiful BRAND NEW lodging units. There are three entertainment 3100 sq ft Reunion Homes which sleep up to 22 people each. The newest four bedroom entertainment reunion homes also have a private outdoor hot tub in the screen porches. Our cabins and homes range in size from extra large one room studio cabins to six bedroom entertainment reunion homes. The cabins and homes also range from BRAND NEW traditional Minnesota studio cabins to BRAND NEW luxury homes. They are all uniquely furnished, designed and accessorized to have that comfortable cozy "Charm of the past with luxury of today", located in the heart of lake country and nature. "White Birch Resort accomodations are truly unique for the Northwest Central region of Minnesota". All of White Birch Resorts cabins and homes have breathtaking Blackduck Lake views, because they sit on a hill 25' above Blackduck lake. The lake front consists of 500'x100' well groomed lawns to the lakes edge. The west side of the resort borders the knee high, Blackduck River which flows north to Red Lake. The total resort sits on 7 acres, so you'll find we have a lot of ample amount of space. WBR is a year round resort for families enjoying fishing, hunting, down hill skiing, ice fishing, hiking, snowmobiling and all around outdoor activities.
We are located just three miles west of Blackduck MN. The little town of Blackduck is approximately 800 people located only 25 miles northeast of Bemidji, MN and 25 miles south of Upper Red Lake. This friendly little town is a Northwoods hub for great outdoor recreation. It also has a variety of businesses and activities to welcome and serve you. We're sure you'll like our Northwoods hospitality for your next Minnesota family vacation! Take some time to explore our website and let us know which BRAND NEW home or cabin you would like us to reserve for your next MN family vacation. Or just feel free to call us and we will be happy to discuss what our resort and Minnesota attractions in the area have to offer. Thank you for viewing White Birch Resort and we hope we can start a Minnesota family vacation for you.
Call to reserve your Minnesota Vacation Lake Home or Cabin<PHONE_NUMBER> Home<PHONE_NUMBER> Cell White Birch Resort Monte and Sandy Sharbono 18882 N Blackduck Lake Rd NE Hines MN 56647


main.ox
Test, example and replication programs have documentation available in the links below
All the code is included with the niqlow package the examples directory
Running Example Programs
You can run sample programs using a menu by executing the program /niqlow/examples/main.ox
INTERACTIVE MODE
The command line would look like this:
PATH/niqlow/examples> oxl -i"../include" main
A menu should appear that looks something like this:
Interactive Menu: Niqlow Test Menu
[00] Run All (excluding sub-options)
[01] DDP Tests & Demos
[02] FiveO Tests & Demos
[03] Replications of Published Work
[04] Hybrid & Miscellaneous
[05] CFMPI Tests & Demos
[-2] Help on Menu
[-1] QUIT
?
Enter numbers to run the test or to enter the sub menu
If running in OxEdit
: Ensure Takes Input
is checked on in the Tools → Add/Remove Modules
menu; Otherwise the keyboard input will be ignored; See a screenshot of the menu setting that allows keyboard input
BATCH MODE
If you know the values you would enter interactively you can add them to command line.
For example: to run all DDP test programs:
PATH/niqlow/examples> oxl -i"../include" main 1 0
Global functions
|
| main |
|
Present a menu of test, sample and replication functions to call; will also read options from
the command line. |
Global
main
main ( )
-
Present a menu of test, sample and replication functions to call; will also read options from
the command line.


First Name
Last Name
Email
Country
Choose a country
United States
Canada
Mexico
England
France
Biography
Phone Number
Affiliations
Occupation
Choose an ocupation
Student
Lawyer
Web Developer
Teacher
Contractor
other
Cat's Name
Favorite Gadget
Type of talent
Choose a talent
Juggling
Walking on stilts
Play guitar
Singing
Dancing
Favorite Drink
Special Power
Weapon of Choice
Comments


This demo comes with
coinbin/coinbin.db sqlite database file.
The database file contains the main
tables cryptprice, cryptcoin,
cryptasset, crypttrade If you want a
clean databse,first close this app
and
rename the coinbin.db file.
Relaunch this app and it wll create a new coinbin.db database
using the file coinbin/dbschema.txt You will then need to do the following
in the defined order: NOT TESTED.!


Siyang's Blog
A Dev Academy Exercise
Home
Blog Post Archive
Pictures
About Me
Resources
Pictures!
Hero image


Number1
Number2
Number3
Number4
Number5
Number6
Number7
Number8
Number9
Number10
Number11
Number12
Number13
Number14
Number15


▪ Task Management
PMApp helps you make projects more manageable by breaking them down into smaller steps and assigning them to team members. Each project can be broken down into milestones, task lists, tasks, and even subtasks. You can give each of these units start and end dates, descriptions, attach relevant documents to them and assign them. Their status can be updated as a percentage completed at any time so you can see their progress. You can see every aspect of a task that you have assigned, or that has been assigned to you in list form. Rather than having tasks spread throughout your email inbox, you can see them all in one place, in a clear hierarchical manner, with their whole history and relation to the larger project including the parent record.
▪ Charts and Reporting
In addition to helping you organize and track the progress of your tasks, PMApp helps you take all the information collected from the tasks making up a project to give you dashboards and reports that help maximize efficiency. Gantt charts and various other charts show a projects interdependent tasks on a grid to show you how much time is scheduled for each task, and which tasks must be completed before a dependent task can be started. Resource utilization charts gives you a bird's eye view of your employees' availability to see who has too much work, and who is free for further tasks. Task reports show you the status of a project's tasks, so you know what percentage of the whole project is done, and where you are in danger of falling behind. In addition, you can customize reports for your own specific needs.
▪ Collaboration Tools
PMApp seeks to make collaboration between those involved in a project easy. Users can post comments, share documents or export to Excel files. It allows you to see project developments on a timeline, so that you can see what other team members are doing daily. In future versions, will offer even more tools. PMApp will be fully integrated with Microsoft Office.


How to install Blender 3D in ubuntu 16.04 ● 03 Jun 2016 Today i am going to show you guys how to install blender with PPA i... console


Here at Sean's Restaurant we serve traditional Irish food that will make you feel like you are in the greener pastures of Ireland.
Content
Sean's Irish Pub began out of a passion for one man's Irish heritage. Sean O'connor is one of a long line of Irish descendants, and nothing resonates more with the culture than some down home Irish food. It's our goal here at the pub to bring you the finest Irish food, in the atomosphere it was designed to be enjoyed at, the pub. We hope you can come by and enjoy all of the comforts of the Old Country here at your local pub.
Place holder for image from DB
PLACEHOLDER FOR THE STORY
PLACEHOLDER FOR THE STORY
PLACEHOLDER FOR THE STORY
PLACEHOLDER FOR THE STORY


WhatsApp conversation analyser
I got the idea for this project during the second year of my masters degree. Two of my close friends - Debbie and Liam - and I had a very active WhatsApp conversation, one that I thought would cover most of my experiences at Oxford. At one point I downloaded the message thread to check the number of words and came up with something around 110,000. We'd basically written a short novel through our phones.
But other than scrolling through it there wasn't an easy way for me to pick out what we'd talked about or find a particular conversation. So I built something to do it.
The web app I built makes use of Rstudio's Shiny package, ggplot, and the visNetwork package. Once you upload a conversation it will show you a number of things. The first is a conversation network - essentially who messaged and who responded - for the entire conversation.
On the second tab it shows word frequency and share of the conversation. I also added in a feature so you can smooth over a number of days.
On the final tab you can search for particular bits of the conversation. Say I wanted to see when we'd talked about breakups. I could search "breakup" and see when the word was mentioned.
Then once I've found the mentions I can enter a particular line number and click over to the "context" tab and see messages either side of the particular mention.
Want to play around? It works with any iPhone based WhatsApp conversation (you can download one in txt form directly from the WhatsApp app).


PolyChrome
PolyChrome is an extension for Firefox web browser that can run Standard ML programs embedded in HTML documents. The extension provides a simple foreign function interface to JavaScript. As a result, JavaScript libraries and interfaces provided by the browser, such as DOM and Canvas, can be used from Standard ML.
Why do this?
- HTML, CSS and browser technologies such as Canvas or Scalabble Vector Graphics support provide Standard ML with a way of creating Graphical User Interfaces or graphics in general.
- Easy deployment of SML applications. If PolyML and PolyChrome is installed, opening the URL (remote or local) of the application is all it takes to run it.
- Cross-platform GUIs (Although Windows is currently not tested and probably requires cygwin).
What are the limitations?
- The JavaScript FFI is rather inefficient therefore applications using this FFI intensively, e.g. rendering animations, might be slow.
- The memory sharing mechanism between JavaScript and Standard ML is not fully automated, which means that some explicit code for memory management is sometimes needed (to prevent memory leaks).
- All ML applications are currently trusted, they could potentially be harmful: we do not currently limit what SML can do on the client machine.
How does it work?
- PolyChrome is composed of two main components. The JavaScript component of the extension (executed in Firefox) opens up a PolyML process, which we call the ML component, for each HTML document.
- A socket connection is established between the JavaScript and Standard ML components.
- DOM, Canvas, etc. libraries are loaded in PolyML.
- Those libraries use the socket connection to forward any JavaScript function call to the JavaScript component, where it get's executed.
- Because the browser provides a JavaScript interface to DOM, we can now access and modify DOM from Standard ML code.
- The SML code from the HTML document is grabbed by the JavaScript component and sent for evaluation to the Standard ML component
- More details are provided in the documentation
PolyChrome in action
About the Project
PolyChrome was developed by Karolis Narkevicius and Lucas Dixon. We'd like to thank EPSRC Platform grant The Integration and Interaction of Multiple Mathematical Reasoning Processes", and the Edinburgh DReaM group for supporting this work. We'd also like to thank David Matthews for his input, ML wizardry, and tireless maintenance of PolyML.


about us
A Seattle institution with locations scatterd throughout the city. We handcraft our small-batch, artisinal products in a derelict fishing vessel ran aground in the Puget Sound. All of our ingredients are sustainably harvested from locally owned Whole Foods dumpsters by our hard working staff of urban foragers. We hope you enjoy our cookies as much as we enjoy crafting them for you.


| Interface and Description |
|---|
| org.apache.bcel.classfile.AttributeReader
Use UnknownAttributeReader instead
|
| org.apache.bcel.Constants
(since 6.0) DO NOT USE - use Const instead
|
| org.apache.bcel.ExceptionConstants
(since 6.0) DO NOT USE - use ExceptionConst instead
|
| org.apache.bcel.generic.InstructionConstants
(since 6.0) Do not use. Use InstructionConst instead.
|
| Class and Description |
|---|
| org.apache.bcel.util.ClassLoader
6.0 Do not use - does not work
|
| org.apache.bcel.util.ClassVector
as of 5.1.1 - 7/17/2005
|
| Field and Description |
|---|
| org.apache.bcel.verifier.structurals.Frame._this
Use the getter/setter to access the field as it may
be made private in a later release
|
| org.apache.bcel.classfile.AccessFlags.access_flags
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.classfile.FieldOrMethod.attributes
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.classfile.FieldOrMethod.attributes_count
(since 6.0) will be removed (not needed)
|
| org.apache.bcel.generic.InstructionFactory.cg
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.classfile.ConstantCP.class_index
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.classfile.FieldOrMethod.constant_pool
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.classfile.Attribute.constant_pool
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.ConstantPoolGen.constants
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.InstructionFactory.cp
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.FieldGenOrMethodGen.cp
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.ElementValueGen.cpGen
(since 6.0) will be made private and final; do not access directly, use getter
|
| org.apache.bcel.classfile.ElementValue.cpool
(since 6.0) will be made private and final; do not access directly, use getter
|
| org.apache.bcel.ExceptionConstants.EXCS_ARRAY_EXCEPTION |
| org.apache.bcel.ExceptionConstants.EXCS_CLASS_AND_INTERFACE_RESOLUTION
Do not use these arrays, use the static methods in the ExceptionConst implementation class instead
|
| org.apache.bcel.ExceptionConstants.EXCS_FIELD_AND_METHOD_RESOLUTION |
| org.apache.bcel.ExceptionConstants.EXCS_INTERFACE_METHOD_RESOLUTION |
| org.apache.bcel.ExceptionConstants.EXCS_STRING_RESOLUTION |
| org.apache.bcel.generic.Select.fixed_length
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.InstructionHandle.i_position
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.CPInstruction.index
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.ConstantPoolGen.index
(since 6.0) will be made private; do not access directly, use getSize()
|
| org.apache.bcel.generic.BranchInstruction.index
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.Select.indices
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.classfile.Attribute.length
(since 6.0) (since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.Instruction.length
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.Select.match
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.Select.match_length
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.LocalVariableInstruction.n
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.FieldGenOrMethodGen.name
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.classfile.ConstantCP.name_and_type_index
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.classfile.FieldOrMethod.name_index
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.classfile.Attribute.name_index
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.Instruction.opcode
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.Select.padding
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.BranchInstruction.position
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.Type.signature
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.classfile.FieldOrMethod.signature_index
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.ConstantPoolGen.size
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.classfile.Constant.tag
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.classfile.Attribute.tag
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.BranchInstruction.target
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.Select.targets
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.classfile.ElementValue.type
(since 6.0) will be made private and final; do not access directly, use getter
|
| org.apache.bcel.generic.Type.type
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.FieldGenOrMethodGen.type
(since 6.0) will be made private; do not access directly, use getter/setter
|
| org.apache.bcel.generic.ElementValueGen.type
(since 6.0) will be made private and final; do not access directly, use getter
|
| org.apache.bcel.util.ClassVector.vec |
| org.apache.bcel.util.ClassQueue.vec
(since 6.0) will be made private; do not access
|
| Method and Description |
|---|
| org.apache.bcel.classfile.Attribute.addAttributeReader(String, AttributeReader)
(6.0) Use
Attribute.addAttributeReader(String, UnknownAttributeReader) instead |
| org.apache.bcel.generic.ReferenceType.firstCommonSuperclass(ReferenceType)
use getFirstCommonSuperclass(ReferenceType t) which has
slightly changed semantics.
|
| org.apache.bcel.generic.FieldOrMethod.getClassName(ConstantPoolGen)
If the instruction references an array class,
this method will return "java.lang.Object".
For code generated by Java 1.5, this answer is
sometimes wrong (e.g., if the "clone()" method is
called on an array). A better idea is to use
the
FieldOrMethod.getReferenceType(ConstantPoolGen) method, which correctly distinguishes
between class types and array types. |
| org.apache.bcel.generic.FieldOrMethod.getClassType(ConstantPoolGen)
If the instruction references an array class,
the ObjectType returned will be invalid. Use
getReferenceType() instead.
|
| org.apache.bcel.generic.Instruction.getComparator()
(6.0) use the built in comparator, or wrap this class in another object that implements these methods
|
| org.apache.bcel.classfile.LocalVariableTable.getLocalVariable(int)
since 5.2 because multiple variables can share the
same slot, use getLocalVariable(int index, int pc) instead.
|
| org.apache.bcel.generic.ObjectType.referencesClass()
(since 6.0) this method returns an inaccurate result
if the class or interface referenced cannot
be found: use referencesClassExact() instead
|
| org.apache.bcel.generic.ObjectType.referencesInterface()
(since 6.0) this method returns an inaccurate result
if the class or interface referenced cannot
be found: use referencesInterfaceExact() instead
|
| org.apache.bcel.classfile.ConstantUtf8.setBytes(String)
(since 6.0)
|
| org.apache.bcel.generic.Instruction.setComparator(InstructionComparator)
(6.0) use the built in comparator, or wrap this class in another object that implements these methods
|
| org.apache.bcel.classfile.StackMapEntry.setNumberOfLocals(int)
since 6.0
|
| org.apache.bcel.classfile.StackMapEntry.setNumberOfStackItems(int)
since 6.0
|
| Constructor and Description |
|---|
| org.apache.bcel.util.ClassPath()
Use SYSTEM_CLASS_PATH constant
|
| org.apache.bcel.classfile.FieldOrMethod(DataInputStream, ConstantPool)
(6.0) Use
FieldOrMethod.FieldOrMethod(java.io.DataInput, ConstantPool) instead. |
| org.apache.bcel.classfile.StackMapEntry(int, int, StackMapType[], int, StackMapType[], ConstantPool)
Since 6.0, use
StackMapEntry.StackMapEntry(int, int, StackMapType[], StackMapType[], ConstantPool)
instead |
Copyright © 2004–2016 The Apache Software Foundation. All rights reserved.


{% extends "base-without-menu.html" %} {% block title %}404 - Page not found{% endblock %} {% block body %}
This is not the page you were looking for.


  We are a non-profitable company. All profits we get from the company goes straight back into buying
more hardware and software to make your experience a much better one.
We offer a variety of deals to all of our customers. Be sure to ask!
Our prices start off at 1.40€/GB RAM. We are always offering deals so be sure to Join our support server today and get your offer from one
of our support team members.
Our mission is to give everyone a chance and opportunity to get a running server going and earn skills in management and business. If you think you are ready to take on this challenge or would like to give it a go but with some assistance, Contact
us today!
We are only taking orders through our discord currently. To make an order or a inquiry. Go to #🤖commands🤖 and do: -new. You will then be taken to a ticket created by our wonderful bot. From there you have 3 choices.
General
Issue | Server issue | Purchase
From there you can choose the appropriate category. In this case, Purchase. After that, follow the tickets instructions.


I'm not that interesting, but in case you were wondering.
Ithaca born and raised, I am a tree loving hippy at heart. I was born 26 years ago in Cayuga Medical Center, considered an "oops baby" by my parents (hopefully a happy accident?). I have lived their my entire life, and could not think of a better place to call home.
Want to learn more about me? Check out my Hobbies and Interests or my Background experience!


W3C XML Schema defines 9 different datatypes for various forms of time-related values. Most of these are not very useful for data exchange between applications. Consider gMonthDay, for instance, which represents a particular month and day of the month without regard to a year - although this could be useful for some specialized applications, most applications need full date specifications including a year. Three of the schema time-related datatypes are widely used for data exchange: dateTime, date, and time. The dateTime datatype is effectively the "core" type, with date and time types just trimmed versions of the dateTime representation.
Unfortunately, the dateTime/date/time datatypes all suffer from one severe limitation when it comes to their use for data exchange: Schema allows the values to be specified either in UTC time (or with a fixed offset from UTC, equivalent to UTC) or without reference to any time zone. The latter case is what usually causes problems for data exchange. Applications always want to work either with fully-specified date/time values, representing a particular instant of time which can be converted at will into any time zone, or with date/time values without reference to time zone (such as a birthday). Very few applications are written to work interchangably with both types of values.
In Java the standard date/time representation uses either a java.util.Date
value or a java.util.Calendar
value. The former corresponds to a
fully-specified dateTime value in schema terms, since it is a specific millisecond in
UTC. The latter has no schema equivalent,
since it includes actual time zone information (rather than just an offset from GMT for
a particular instant of time, as allowed by the schema representation). Various methods
are used by different data binding tools to convert these two Java types to and from
XML representations, but no method can correct the inherent differences.
Because of these issues of date/time representations in schema, and the problems in matching the schema datatypes to Java types, JiBX supports working with both standard Java classes and Joda date/time classes. The Joda library provides a much richer set of representations for date/time values than standard Java, and the richer representations allow more ways of handling the conversions. This still doesn't correct for the fundamental flaws in the schema representation of date/times, but it at least allows you to easily control how the conversions are handled for your code.
The following table gives the full range of date/time formats built into the JiBX handling, including both default formats (as indicated) and formats you can specify by name for use in your bindings:
| Type | Format Label | Conversion |
|---|---|---|
java.util.Date |
Date.default | Converts instances of |
java.sql.Date |
SqlDate.default | Converts instances of |
java.sql.Time |
SqlTime.default | Converts instances of |
java.sql.Timestamp |
Timestamp.default | Converts instances of |
org.joda.time.LocalDate |
LocalDate.default | Converts instances of |
org.joda.time.DateMidnight |
DateMidnight.zoned | Converts instances of |
org.joda.time.DateMidnight |
DateMidnight.local | Converts instances of |
org.joda.time.DateMidnight |
DateMidnight.UTC | Converts instances of |
org.joda.time.LocalTime |
LocalTime.local | Converts instances of |
org.joda.time.LocalTime |
LocalTime.UTC | Converts instances of |
org.joda.time.DateTime |
DateTime.zoned | Converts instances of |
org.joda.time.DateTime |
DateTime.UTC | Converts instances of |
org.joda.time.DateTime |
DateTime.local | Converts instances of |
org.joda.time.DateTime |
DateTime.strict-local | Like the DateTime.local conversion, above, but requires time zone information in schema dateTime values being deserialized (throwing an exception if no time zone information is present). |
org.joda.time.DateTime |
DateTime.strict-UTC | Like the DateTime.UTC conversion, above, but requires time zone information in schema dateTime values being deserialized (throwing an exception if no time zone information is present). |
The actual implementations of the conversions for standard Java date/time classes
are in the org.jibx.runtime.Utility
class, while those for the Joda
date/time classes are in the org.jibx.runtime.JodaConvert
class. You can
use the methods in these classes to construct your own custom combinations of
serialization and deserialization handling.


"Light Makes Right"
July 16, 2000
Volume 13, Number 1
Compiled by Eric Haines, 1050 Craft Road, Ithaca, NY 14850<EMAIL_ADDRESS>. Opinions expressed are mine, not Autodesk's.
All contents are copyright (c) 1999-2000, all rights reserved by the individual authors
Archive locations: text version at
http://www.acm.org/tog/resources/RTNews/text/
HTML at
http://www.acm.org/tog/resources/RTNews/html/
You may also want to check out the Ray Tracing News issue guide and the ray tracing FAQ.
The most significant news in ray tracing this year is the publication of Peter Shirley's book, Realistic Ray Tracing. See it at AK Peters' booth (#2621) at SIGGRAPH. Briefly paging through the book, it looks clear and precise, with many helpful illustrations and figures - more about it next issue. Really, though, you should just buy it; it brings together many disparate bits of information, especially on shading, sampling, and filtering. Pete says the book's subtitle could have been, "how Pete Shirley implements a ray tracer". He's too modest: the book looks like it gives a solid education in some of the foundations of the field, and all in 161 pages. At first I thought this a bit short, but I think that's just a sign of the effect of book selling psychology: some publishers like to sell trade paperbacks that are 1200+ pages, regardless of usefulness of the text, in hopes of looking authoritative. This book focuses on equations, which is a more dependable (and compressed) way to explain something than just pure text alone (I think of it like code vs. comments; code can be terse, but it is a more reliable source for what the program actually does than the comments about the code).
Other books I'm looking forward to: Dave Eberly's Game Engine Design, (Morgan-Kaufmann Publishers) which looks to have much useful information and code in it, see http://www.magic-software.com/3DGameEngineDesign.html (also, Dave's site http://www.magic-software.com/ is a national treasure). Mark DeLoura's Game Programming Gems (no relationship to the Graphics Gems series; from Charles River Media) collection sounds interesting, judging from the articles I've heard it will contain. Mathematics for Computer Graphics Applications by Michael Mortenson (Industrial Press) is another book which I want to look at. Another I'll definitely consider is David Rogers' An Introduction to NURBS, from Morgan-Kaufmann.
Another relatively new book worth getting is Apodaca and Gritz's Advanced RenderMan book. Even if you do not have any interest in RenderPerson itself, this book has much to recommend it, both from an algorithms standpoint and in learning about techniques used in motion pictures. I've also been enjoying Visual Intelligence: How We Create What We See by Donald Hoffman. It gives an overview of results in perceptual psychology for us ignoramuses, and does so without dumbing down the material. There are also copious references to the research the author draws his text from.
In case you missed it, the coolest graphics-related thing on the web this past half year is sodaconstructor: http://www.sodaplay.com/. The most insane graphics-related thing is Donkey Kong for the Kodak Digita digital camera: http://digita.mame.net/. The best user interface ever is at http://www.cs.unm.edu/~dlchao/flake/doom/. The Fantasy Graphics League results are at http://www.realtimerendering.com/fgl/. Hardest way to earn a million dollars: http://www.ams.org/claymath/. The most useful free web service I've found this year has been http://www.spyonit.com/; set up any URL you want for it to track, and the service will email you when the page has changed. It's great for seeing when a conference schedule gets posted, when new software has become available, when an annotated links page has been updated, etc. (Thanks to Craig Reynolds for this tip; he's an absolute links fanatic: http://www.red3d.com/cwr/links.html).
The other useful goodie has been GuruNet http://www.gurunet.com/, a free service that I use only occasionally but is wonderfully unobtrusive. Don't know a word, or exactly how to spell it, or just want to know about something? Hold down the Alt key and click on it and GuruNet pops up and tells you (after a few seconds of obligatory net delay), as well as giving thesaurus, encyclopedia, news, business summary, translations, and other relevant entries for the word. What's cool is that GuruNet cooperates with every program that has text that can be selected, not just web pages, so you just have to learn a single, trivial action and it simply works everywhere.
For the first time ever, I've noticeably changed a previous issue of the Ray Tracing News. I normally avoid doing this, disliking the "1984" concept of rewriting the past (definitely easy to do with web documents). This time it made sense to do so: Vlastimil Havran sent some updates to his octree summary article in RTNv12n2, and these have been folded in.
A puzzle invented by Paul Strauss: you're given a square sheet of paper, one side is blue and the other red. You can make folds in the paper, but the rule is that only red can touch red. Red touching blue or blue touching blue will destroy the entire universe. Folds are full 180 degree foldovers, so some piece of paper will always touch another part of the paper. So, what is the maximum number of folds you can make? There are no tricks here, it's just a straightforward puzzle. Hint: the answer is > 4 and < infinity.
Last issue's puzzle was: You have a cube and you select at random three (different) corners. What is the chance that the triangle formed by these corners is acute (all angle < 90 degrees)? is a right triangle (has one angle == 90 degrees)?
A quick answer is this (from Spike Hughes): there are 8*7*6 possible triangles, and divide by 3*2 since we do not care about the order of the vertices. This gives 56 unique triangles formed. Of these, 6 have right angles at a given corner: the 3 cube-edge/cube-edge pairs and the 3 edge/perpendicular-face-diagonal pairs. Each triangle can have at most one right angle, so with 6 right triangles at a given corner, then 6*8=48 triangles must be right triangles. So 48 of 56, i.e. 6 of 7 triangles formed are right triangles. This leaves a 1 in 7 chance that a random triangle is acute. No obtuse triangles are possible, interestingly enough. Other ways of thinking about this problem include proving that acute triangles must be formed entirely of cube face diagonals, and using dot products of 0 between edges to rule out right triangles.
back to contents
http://www.graphics.cornell.edu/~phil/GI/
- Phil Dutre<EMAIL_ADDRESS>[This thing's amazing, go grab it. -EAH]
_______
3D Object Intersection page
A page giving references a wide variety of 3D object intersection references is now available:
http://www.realtimerendering.com/int/
Also at this site is my personal list of frequently used graphics related web sites:
http://www.realtimerendering.com/portal/
It's geared towards real-time rendering, but has much that applies to graphics in general.
________
Optimizing Ray-Triangle Intersection
If you're interested in optimized ray-triangle intersection code and statistics, then take a look at:
http://www.ce.chalmers.se/staff/tomasm/raytri/
I have optimized my and Trumbore's code from journal of graphics tools, and tried it on three different machines and with different percentages of triangle hits. The code is also available at the above mentioned site. Let me know if you have any suggestions for improvements.
-- Tomas Moller<EMAIL_ADDRESS>________
Graphics Gems Repository update
The Gems repository has been expanded in two ways. New pages have been added:
http://www.acm.org/tog/GraphicsGems/category.html - by category http://www.acm.org/tog/GraphicsGems/authors.html - by author http://www.acm.org/tog/GraphicsGems/gems.html - in book order
In addition, each of these pages has direct links to the relevant code for each gem.
________
Non-Photorealistic Rendering
Craig Reynolds maintains an excellent annotated links collection on the subject of NPR:
http://www.red3d.com/cwr/npr/
________
SIGGRAPH has the beginnings of a corrigenda (i.e. corrections) site for SIGGRAPH proceedings:
http://www.siggraph.org/publications/corrigendum.html
If you know of an error in a SIGGRAPH article, please let Stephen Spencer<EMAIL_ADDRESS>know.
This year's SIGGRAPH papers are listed and online versions linked from:
http://www.cs.brown.edu/~tor/sig2000.html
________
A mailing list dedicated to realtime raytracing now exists:
You can join this community by going to:
http://www.onelist.com/subscribe/realtime_raytracing
Or you can join by sending email to:
<EMAIL_ADDRESS>The archives are at:
http://www.egroups.com/group/realtime_raytracing
This list has had some interesting discussions (see some later in this issue), though traffic has died down in recent months. Many of the subscribers are into the demo scene (see http://www.acm.org/tog/resources/RTNews/demos/overview.htm).
________
The Best Efficiency Scheme (BES) Project has its own page at:
http://www.cgg.cvut.cz/GOLEM/bes.html
The WWW page contains updated version of the project proposal, more than 200 possible scenes in VRML'97 format of different complexity, and technical report describing the first results of the project (testing on 30 SPD scenes X 12 acceleration data structures X 4 methods of shooting rays).
By the way, we are still looking for large scale scenes (over 500,000 primitives).
-- Vlastimil Havran<EMAIL_ADDRESS>________
A software tool for interactive visualization of spatial data structures was designed to verify the correctness of implementations. Several static images from that visualization are available at:
http://www.cgg.cvut.cz/~havran/vis/visualization.html
-- Vlastimil Havran<EMAIL_ADDRESS>[This is pretty interesting to look at, in fact. -EAH]
________
Art of Illusion
Art of Illusion is a free, open source 3D modelling and rendering studio. It is written entirely in Java, and should be usable on any Java Virtual Machine which is compatible with JDK 1.1 or later.
The current version is 0.4, released May 3, 2000. This is still a fairly early version, and some basic functionality is still missing. It is progressing quickly, however, and already has a number of advanced features including a powerful raytracer, a flexible and easy to use triangle mesh editor, and the ability to automatically generate smooth, organic shapes from triangle meshes.
http://drizzle.stanford.edu/~peastman/aoi.html
-- Peter Eastman<EMAIL_ADDRESS>[Peter also notes that this package has a triangulator in it: "The routine is Line.convertToTriangleMesh. I can't guarantee that it's the best algorithm, but it seems to work pretty well. Also, it will deal fine with concave polygons, but will sometime have trouble with self-intersecting ones."]
________
Real-Time Volumetric Rendering
We did some volumetric rendering with raytracing and then "mixed" that with a normal 3d scene (the scene was drawn using 3d acceleration).
Fair enough, it looks a bit blurry but it does give the impression of flying through 3d clouds.
Oh you can download the demo from http://www.incognita-hq.com if you're curious. it's called platipus (needs a "multimedia" machine with dx7, ram, the whole lot).
In the demo there's also my (now pretty old) rt engine, which is not too bad.
-- angel sastre<EMAIL_ADDRESS>[Also, source code is available at the site.]
________
Year Three (1998/1999) results of the Internet Raytracing Competition are now available on CD ROM. The quality of some of the winning entries is impressive:
http://www.irtc.org
________
The global illumination bibliography now resides on:
http://www.helios32.com/
as well as other related resources. There's also an image of the very first radiosity image ever computed (made with hand-cranked calculators). See http://www.helios32.com/resources.htm#History
________
Some interesting BIBTEX entries of lesser known papers can be found at:
Ray tracing: http://www.cgg.cvut.cz/~havran/Bib/rtmame.bib Visibility: http://www.cgg.cvut.cz/~havran/Bib/vismame.bib Rendering: http://www.cgg.cvut.cz/~havran/Bib/renmame.bib
The lists are being regularly updated with new papers as they appear.
-- Vlastimil Havran<EMAIL_ADDRESS>________
An extensive annotated collection of links to procedural texture synthesis is available at:
http://www.threedgraphics.com/texsynth/
________
The PVMPOV patch gives POV-Ray the ability to distribute a rendering across multiple Unix platforms:
http://www-mddsp.enel.ucalgary.ca/People/adilger/povray/pvmpov.html
There is also a beta Win32 version at:
http://netlib2.cs.utk.edu/pvm3/win32/
________
A nice summary of free L-system software out there is at:
http://www.cpsc.ucalgary.ca/projects/bmv/software.html
________
A pleasant page covering free and shareware modeling software:
http://www.mech.ed.ac.uk/~dom/3d/3d.html
________
John Morris' lecture notes for his data structures class are nicely done, covering the basics of this subject. Worth a look at:
http://swww.ee.uwa.edu.au/~plsd210/ds/
________
The mental ray specifications are interesting to read from a standpoint of looking at what features are part of a commercial ray tracing renderer:
http://www.mental.com/p207.html
________
In response to several requests, we have made available measured skin BRDF data from the 1999 EGWR paper,
"Image-Based BRDF Measurement Including Human Skin", by Steve Marschner, myself, Eric Lafortune, Ken Torrance, and Don Greenberg.
Data are in gzipped tar archives, each with a lot of binary data files containing raw BRDF samples in red, green, and blue channels. Data on the spectral response of the camera and the spectral balance of the source are included, and two of the three data sets include coefficients for rendering with the multi-lobe representation of Lafortune et al. (SIGGRAPH 97).
The URL is http://www.graphics.cornell.edu/online/measurements/
Have fun.
-- Stephen H. Westin<EMAIL_ADDRESS>________
The Mops is a free open source modeler for Unix (Linux, IRIX) systems and (sort-of) Windows. Check it out at:
http://www.informatik.uni-rostock.de/~rschultz/mops/
________
A great site for information on implicit surfaces is:
http://implicit.eecs.wsu.edu/
On a related note, Jules Bloomenthal's very useful implicit surface polygonizer article from Graphics Gems IV is now also available at his site:
http://www.unchainedgeometry.com/jbloom/papers/index.html
________
GraphicsJungle
At:
http://www.cpsc.ucalgary.ca/Redirect/GJ/index.html
is the Jungle project, run by Przemyslaw Prusinkiewicz and Brian Wyvill. It is focussed on modeling, animating and rendering blobbies. The software can be found at:
http://www.cpsc.ucalgary.ca/~jungle/software/jspdoc/index.html
for SGI and Linux systems.
________
Robert Schneiders maintains an overwhelmingly large annotated links site on mesh generation:
http://www-users.informatik.rwth-aachen.de/~roberts/meshgeneration.html
________
The NURBS++ Package is source under GPL for manipulating and evaluating NURBS curves and surfaces. It includes an OpenGL-based editor, and can output POV-Ray, RIB, or VRML files. It's at:
http://yukon.genie.uottawa.ca/~lavoie/software/nurbs/feature.shtml
________
A few useful resources are at:
http://www.cs.utexas.edu/users/atc/downloads.html
A.T. Campbell, III's page.
________
The POV-Ray SuperPatch is an unofficial collection of extensions to POV-Ray:
http://www.geocities.com/Athens/Academy/8764/spovraydjgpp.html#superpatch
Extensions include parametric surfaces, isosurfaces, splines, sphere sweeps, new pigment mappings, rational bezier surfaces, new mesh type, slope dependent textures, variable reflections, light groups, spherical/toroidal/ (etc)/ warps, and unicode text.
________
For a rundown of tools for POV-Ray, and other open source modeling and rendering software (as well as some nice images), see:
http://www.linuxgazette.com/issue53/gx/baptista/2.html
________
ParPov is a library for reading POV-Ray files. The first application of this library is Pov2Rib, a (surprise) POV to RenderMan RIB format converter. Open source at:
http://www9.informatik.uni-erlangen.de/~cnvogelg/pov2rib/index.html
The quality of the conversion looks to be quite high, see:
http://www9.informatik.uni-erlangen.de/~cnvogelg/pov2rib/examples.html
for comparison images.
________
A basic particle system animator for POV-Ray (with source) is available at:
http://www.sbox.tu-graz.ac.at/home/a/ahi/particle-system.html
________
Hugo Elias' "The good-looking textured light-sourced bouncy fun smart and stretchy page" has some nicely done tutorials on Perlin noise, clouds, physically based animation, and many other tidbits:
http://freespace.virgin.net/hugo.elias/
________
OpenDX
Based on IBM's Visualization Data Explorer, this is an open source visualization package:
http://www.opendx.org/
________
Graphics Course Notes
By Steve Seitz, Paul Heckbert, Andy Witkin, Joel Welling, the notes at:
http://www.cs.cmu.edu/afs/cs/academic/class/15462/web/notes/notes.html
have some interesting tidbits in them. For example, in the Ray Casting section there is a clear explanation of barycentric coordinates, and a cute geometric proof of the formula for the area of a triangle (I haven't seen it before).
________
The Graphics Muse columns in the Linux Gazette has all sorts of tidbits:
http://www.linuxgazette.com/issue46/gm.html
and see the bottom of the page for links to previous issues.
________
For some pleasing images of fractal terrain, see:
http://www.fractalworlds.com
________
Information on IGES, STEP, and other CAD related formats is available at:
http://www.cadcamcenter.com/cadcam/toc.htm
There are also links to other resources of interest to CAD programmers.
back to contents
Description of BART
Abstract: Due to the advent of ray tracing at interactive speeds and because there is an absence of a way to measure and compare performance and quality of ray traced scenes that are animated, we present an organized way to do this fairly and accurately in this proposal for BART: A Benchmark for Animated Ray Tracing. This is a suite of test scenes, placed in the public domain, designed to stress ray tracing algorithms, where both the camera and objects are animated parametrically. Equally important, BART is also a set of rules on how to measure performance of the rendering. We also propose how to measure and compare the error in the rendered images when some kind of approximation algorithm has been used.
Informal description: We were and still are interested in efficient algorithms for computer graphics. In this case we focused on ray tracing algorithms for animated scenes. The main reason for this is that real-time or interactive ray tracing is quite possible to do on multiprocessor computers. So, to be able to compare different acceleration schemes, we set out to compile a suite of test scenes for this. We currently have three scenes described below that we have put into the public domain. Each scene was designed to stress ray tracing algorithms in general. In order for the user of BART to make a fast implementation, we provide a simple C-parser for the file format (it takes about half a day to implement), and some animation code. The benchmark may also be used to: 1) compare algorithms using polygon rendering hardware (e.g., OpenGL), 2) compare global illumination and radiosity algorithms, 3) compare motion blur algorithms, but was not designed specifically for these areas of interest.
The BART benchmarks are at http://www.ce.chalmers.se/BART/.
back to contents
Global Illumination Test Scenes
University of Utah Technical Report UUCS-00-013
Abstract:
The global illumination community has discussed having a database of scenes that could be used to compare and validate different global illumination algorithms. We present a set of test scenes for global illumination algorithms and propose that they be the beginning of such a database. These scenes are designed to be as simple as possible and still test a particular aspect of energy transport. The scenes are available on a web site in a variety of formats, along with images and pixel radiance data. We feel that the simplicity and availability of the models will make it easier for the community to use them, and that the field will benefit from a standard set of scenes. Additionally, we discuss classes of models with analytic solutions.
Tech Report: http://www.cs.utah.edu/~bes/papers/scenes/ Scene Repository: http://www.cs.utah.edu/~bes/graphics/scenes/
back to contents
Ádám Nagy writes:
For intersecting decisions I always use 2 kind of 'Intersection' calculation:
- First is for rays with 1 fixed point. This is true for eye rays, and shadow rays also. This is much simpler for all primitives, because I precalculate coefficients which only depends on the fixed point of the ray, and the primitive.
- Second is the general intersection calculation, which I use only at reflections and refractions.
With a lot of light sources the number of shadow rays + number of eye rays can be so great that this kind of optimization is important.
I use basically sphere hierarchy, but for eye rays in addition I use another special optimization: I divide the screen into sectors (16*16) pixels: for all the sectors I precalculate its own sphere hierarchy which it intersects: I don't have to go through all the hierarchy for all the pixels.
I use adaptive techniques: I do full raytracing for some gridpoints on the screen, and for other pixels I do some heuristics (determined from the neighbor pixel infos) to save costly full hierarchy 'Intersect' calls. I am interested what kind of heuristics other guys are using.
My engine is a little bit slow because it is still in C++, but now I am in the middle of rewriting the important part to PIII Streaming SIMD based assembly code, I'm sure it will help a lot in terms of speed.
My basic idea regarding pIII Streaming SIMD is to maintain an 'Intersecting job queue', and I try to solve 4 intersect job in parallel fully using the PIII Streaming SIMD extensions. Does anyone have experience regarding to optimizing to PIII, or optimizing to Athlon?
Does anyone have experience in doing some part of ray tracing using integers instead of floating point?
Do you know better way than hierarchical spheres, and other kind of optimization techniques?
________
Ádám Nagy later adds:
I am trying to experiment with more complex heuristics, and I am interested in others' ideas about it. Here I show a very basic one, which is already implemented in my engine:
Let's do a classic raytracing for every fourth pixel (I put 1 where I do raytracing.)
10101010 00000000 10101010 00000000 10101010
Let's also store the trace information for those pixel. What does this mean? If for a pixel the eye ray intersected object A, and for the two lightsources the shadow rays intersected object B and object C, and the reflection ray intersected object D, we can store: A(BC)D. After it for the remaining pixels we can check its four neighbors, and if all the neighbors have the same stored structure, than we can simply assume that structure for that pixel without doing any intersecting calculation. In this case the only problem is that we sometimes miss some one-pixel objects, but these are not important (sometimes it is better not to show 1 pixel objects!)
____
Eric Haines replies:
That's an interesting approach, of knowing in advance what the ray tree is and shooting the rays only at those objects. Have you compared shooting the rays for the other 3 neighbors vs. just interpolating the already computed shade across the four corners? Interpolation would be bad if there are textures or a sharp specular highlight, I guess, but otherwise might be fine.
____
Ádám Nagy replies:
Actually, the best approach seems to make a compromise: I do not interpolate the pixel color directly, but I am not shooting the ray to the object: I am interpolating the normal vector (to enable shooting refraction rays...), the shade without texture, and the texture coordinates, and I multiply the texture color with interpolated shade: The textures look fine!
____
Russel Simmons responds:
You don't really need to interpolate the normal vector. I believe the 'standard' approach for grid-based raytracing (and the technique that I use in my engine) is just to treat rays that have been reflected no differently from other rays. In other words, your grid-interpolator routine knows nothing of rays being reflected rays or not; it merely interpolates shade, u, v, across the block. The higher-level tracing routines handle reflections. In addition to shade, u, v, I also store an id for each block. The id is essentially a surface id used to determine which texture to use, and also whether or not a block can be interpolated. If the 4 id's at the corners don't match, I don't interpolate the texture. Now, in the case of reflections, it would be possible to have 3 corners of a block hit object A, but the last corner hit object B, get reflected, finally hitting object A. Even though all 4 corners have the same surface id (of object A) we don't want to interpolate across (because there is an edge between object A and B in there somewhere). So to solve this problem you can flip some high bits in the id value if the surface is hit via a reflection - then the id's won't match. Also, if you want to not interpolate across shadow boundaries (you might want to subdivide) then a decent hack is to have a high bit in the id values represent in/out of shadow.
Getting back to normal vectors.. interpolating them like you say may have some advantages, but in my experience the method described above works and looks great.
____
Paul Kahler notes:
I find the following pattern works really well:
00100010001<PHONE_NUMBER>0<PHONE_NUMBER>0<PHONE_NUMBER>0<PHONE_NUMBER>1
It's every 8th pixel, but my perception is that it's no worse than the 2x2 method you mentioned. That varies with texture, of course. At one point I did tests with a single object and found a disturbing amount of time being spent comparing colors of pixels and interpolating (I just tested color to see if more rays were needed, and interpolated just color) than tracing rays. I came up with a couple of great macros to compare and interpolate colors that cut the time way down - they're like MMX, but in C.
____
Factory responds to Paul's note:
I assume that interpolates along triangles, as opposed to being along parallelograms, i.e.
00111110001<PHONE_NUMBER>0<PHONE_NUMBER>0<PHONE_NUMBER>0<PHONE_NUMBER>1
and not..
11111110001<PHONE_NUMBER>0<PHONE_NUMBER>0<PHONE_NUMBER>0<PHONE_NUMBER>1
> I came up with a couple of great macros to compare and interpolate
> colors that cut the time way down - they're like MMX, but in C.
Hmm, looks like a nasty thing to optimize, I'd prolly try and make special case renderers for the four different rows that need to be rendered.
Another thing bad about that approach is that it prolly wouldn't lend itself to super sampling, but OTOH, I reckon it would look rather kewl if one was to do it with fairly large triangles.. (at least in a demo).
____
Paul replies:
No, actually if I follow your notation correctly it's:
231323132 343434343 Where the 2's are the average of 4 1's 132313231 The 3's are the average of a 2 and a 1 343434343 And the 4's I forgot how they work ;-) 231323132 probably just an average of 2 pixels (hmm which ones..)
Looking at this little diagram makes me think I'm not even averaging the best choices of pixels. OTOH I don't do weighted averages. Also, if the threshold for deciding to shoot more rays is low enough it doesn't mater how you interpolate. BTW, I'm doing this in windows with a default size of 512x384, so the pixels are small and the artifacts are not too bad. Shadows tend to look low-res because the outline of the shadow doesn't always trigger enough additional rays, but at higher speeds you still don't notice. The key is to always shoot rays along an objects edge. With solid colors, just about any interpolation will do for the interior.
____
Bruno Schödlbauer also responds to Paul's comments:
One thing you might try is not to interpolate, but instead to trace one frame every odd pixel, and next frame every even pixel. For every pixel not traced use the values of the previous frame. It probably looks strange with few frames per second, but with many frames one shouldn't notice it.
____
Paul ends on this note:
I just posted 3 small (72K) programs demonstrating my RTRT progress. Also available is an explanation of how I do my pixel interpolation - see the page describing DRE linked from the RTRT page (http://www.oakland.edu/~phkahler/rtrt/dre.html). All found at:
http://www.oakland.edu/~phkahler
Choose the Realtime Raytracing link. BTW, these are Windoze programs and should run on 95,98, or NT unless there is some MFC dll version issue (I've seen some problems before).
You'll notice that my focus is not on getting the best possible performance on a particular scene, but on making a very high performance ray tracer that can be used for all sorts of things. Comments are welcome of course.
back to contents
Nicolas Delalondre wrote:
What is the fastest way to generate eye rays? (I don't want to apply a matrix to each vertex of the scene)
Fastest? There typically is no single fastest way to do anything in computing. Also, it seems highly unlikely that a single matrix-vector multiply is a major cost in your ray tracer.
However, try this:
Take the eye point and the projection plane and transform them into world space. Now simply march along the projection plane for each pixel, this gets you one point and the eye point is another for an eye ray. Viola! If your model & view transforms are nice (exercise to the student to determine what those conditions are...) then you can march along the projection plane for the cost of a single vector addition, and generating the eye ray costs another vector addition (if you need a normalized eye ray, that costs a little extra).
back to contents
Here's my take on transforming planes that should make everything clear. If you represent points as column vectors (that is, translation components in the last column of a 4x4 matrix), then you transform a point by performing the matrix multiply M P = P', where M is the transformation matrix and P is the column-vector point. Given a plane Q, you'd transform by the same matrix by performing the matrix multiply Q M* = Q', where M* is the inverse of matrix M, and Q is a row vector [A B C D], where the plane is defined by Ax + By + Cz + D = 0.
Also note that Q M* = M*t Qt, where M*t is the transpose of M*, and Qt is the column vector form of Q. This is useful if your matrix multiply routine is geared to doing column-vector style multiplication.
If your system uses row-vectors to represent points, then just flip all of the matrix equations I've written above: P' = P M, Q' = M* Q = Qt M*t.
For a quick proof, consider that you want the plane equation Ax+By+Cz+D = 0 to hold true both before and after a transform. That is, for all points P that lie on the plane Q, then all of the transformed points P' should lie on the transformed plane Q':
[1] (Q') (P') = Q P (it's an exercise to the reader to prove that the matrix product of the row vector Q and the column vector P expresses the plane equation Ax+By+Cz+D=0)
[2] (Q M*) (M P) = Q P (Q' = transform Q, and P' = transform P)
[3] Q (M* M) P = Q P (Associative law for matrix multiplication)
[4] Q P = Q P (M* M = Identity)
Q.E.D.
back to contents
However, the Plücker intersection test can also be used to generate the barycentric coordinates. Paraphrasing from [1], given the Plücker coordinate R of a ray through points P0,P1 and the Plücker coordinates E0,E1,E2 for the edges of a triangle (A,B,C), the intersection test checks the signs of the permuted inner products of R and each of E0,E1,E2. If the signs agree, then the ray intersects the triangle.
The permuted inner product of the Plücker coordinates of two lines, P0->P1 and Q0->Q1, is related to the volume of the tetrahedron formed by (P0,P1,Q0,Q1). The volume of this tetrahedron (within a constant scale) is given by the determinant |P0 P1 Q0 Q1|:
| P0.x P0.y P0.z 1 | | P1.x P1.y P1.z 1 | | Q0.x Q0.y Q0.z 1 | | Q1.x Q1.y Q1.z 1 |
The Plücker coordinates of the line P0->P1 are the determinants of the six 2x2 sub-matrices of:
( P0.x P0.y P0.z 1 ) ( P1.x P1.y P1.z 1 )
The connection between the Plücker coordinates and the volume determinant is easy to see, and it can be shown that the permuted inner product is equivalent to |P0 P1 Q0 Q1| [3]. (I have assumed that the w coordinates for the points are 1, for reasons explained below.)
Getting back to the triangle intersection test, given the ray P0->P1, any
point P2 on the ray, and an edge Q0->Q1 of the triangle (A,B,C), it can also
be shown that the volume of the tetrahedron (P0,P1,Q0,Q1) is proportional
to:
- The magnitude of (P0-P1)
- The dot product of (P0-P1) and the normal of (Q0,Q1,P2)
- The area of the triangle (Q0,Q1,P2)
The first factor above is the same for each edge. If we assume (without loss of generality) that P2 is in the plane of the triangle (A,B,C), then the second factor is also the same for each edge, since then the normal of (Q0,Q1,P2) is the same as that of (A,B,C).
Therefore, the volume of the three tetrahedra, and by extension the Plücker inner products of the edges and the ray, are proportional to the areas of the triangles (A,B,P2), (B,C,P2) and (C,A,P2). If P2 is in the plane of (A,B,C), then these are the subtriangles that define the barycentric coordinates of P2. Since the other two factors are the same for each edge, the Plücker intersection test gives (directly) the unnormalized (homogeneous) barycentric coordinates of the ray-plane intersection point.
There is one caveat: although the Plücker coordinates are homogeneous, for the equivalence to hold true, the Plücker coordinates of the edges of the triangle cannot be scaled independently.
(Another benefit to using the Plücker intersection test is explained by Amanatides and Choi[4], where tests are performed only once per edge and shared by adjacent triangles.)
[1] http://www.acm.org/tog/resources/RTNews/html/rtnv10n3.html#art11
[2] http://www.acm.org/tog/resources/RTNews/html/rtnv11n1.html#art3
[3] My thanks to Pat Hanrahan, who explained the equivalence of the
tetrahedral volume and Plücker inner product as well as the
connection to barycentric coordinates after I had found it by
other (less clear) means. He knew of this connection well before
I noticed it.
[4] http://www.cs.yorku.ca/~amana/research/mesh.pdf
John Amanatides, Kia Choi "Ray Tracing Triangular Meshes",
Proceedings of the Eighth Western Computer Graphics Symposium
April 1997, pp 43-52.
(Two related articles are in RTNv15n1.)
back to contents
I just thought I'd mention that I tried some very limited RT volume rendering. I used an oct-tree (however you spell that) and treated it as nested bounding *spheres*. A single sphere is circumscribed around the top level cube in the tree. Then 8 smaller spheres are circumscribed around the 8 subcubes. This pattern is repeated down to the smallest size sphere/cube to be used.
There really aren't any cubes or spheres defined. Only the orientation of the entire hierarchy. Each node in the tree has just 8 pointers to its children (NULL if an octant is empty). The bottom level objects have color information instead of pointers. You can use the recursive structure to do really fast intersection tests on the spheres. The ultimate may be to project the ray onto a plane perpendicular to the ray with the bounding sphere at the origin. The intersection test is then checking if the point is inside a circle, and subsequent tests of the children are just a matter of moving that point around the plane (via 8 vectors projected onto the plane).
I never got as far as the plane projection, but I did do a recursive intersection test and used one of 8 different orders to test the child octants depending on the ray direction (not optimal, but never used the worst-case order). I was able to trace a solid block of 64x64x64 balls at 1 fps or so. There was a LOT of aliasing going on because I was using the normal vector of each ball where the ray hit rather than some type of "surface normal" involving the overall surface geometry.
My conclusion was that each voxel should have a single normal vector associated with it (I've used this before in a non-RT voxel renderer http://www.oakland.edu/~phkahler) and with more optimization you could get good performance and large voxel counts. I've decided to put that aside until several gigabytes of ram are available and I have more time. RAM usage can be minimized if you can re-use even the smallest subtrees but a complex scene will still require a lot of storage and it will be static (those blades of voxel grass will not blow in the wind).
back to contents
Vlastimil Havran writes:
Several papers on ray tracing appeared at WSCG'2000(http://wscg.zcu.cz/wscg2000/wscg_2000_program.htm), SCCG2000(http://www.dcs.fmph.uniba.sk/~sccg/2000/program.htm), and EGWR 2000(http://www.fee.vutbr.cz/egrw2000/program.html), that could be of interest. I've selected only those closely related to ray tracing (many more of them are related to general rendering, particularly to global illumination):
Wilkie,A., Tobler,R.F., Purgathofer,W.: Raytracing of Dispersion Effects in Transparent Materials (Austria) http://wscg.zcu.cz/wscg2000/Papers_2000/W7.pdf.gz
Havran,V., Dachs,L., ra,J.: VIS-RT: A Visualization System for RT Spatial Data Structures (Czech Republic) http://wscg.zcu.cz/wscg2000/Papers_2000/X77.ps.gz
Revelles,J., Urena,C., Lastra,M.: An Efficient Parametric Algorithm for Octree Traversal (Spain) http://wscg.zcu.cz/wscg2000/Papers_2000/X31.pdf
Poitou,O., Bermes,S., Lecussan,B.: Laziness, a Way to Improve Distributed Computation of the Ray Tracing Algorithm http://wscg.zcu.cz/wscg2000/Papers_2000/T29.ps.gz
EGRW 2000:
Dynamic Acceleration Structures for Interactive Ray Tracing, Erik Reinhard, Brian Smits, Chuck Hansen
Direct Ray Tracing of Displacement Mapped Triangles, Brian Smits, Peter Shirley, Michael Stark
Ray Tracing Point Sampled Geometry, Gernot Schaufler, Henrik Jensen
Tapestry: A Dynamic Mesh-based Display Representation for Interactive Rendering, Maryann Simmons
________
What follows are abstracts which I (Eric) have collected from email, etc; by no means is it a comprehensive list.
Reinhard, E., Smits, B., and Hansen, C., "Dynamic Acceleration Structures for Interactive Ray Tracing," in Proceedings Eurographics Workshop on Rendering, (Brno, Chzech Republic), June 2000.
My own explanation: The idea of this paper is that as objects move outside the grid efficiency structure, they are (cheaply) reinserted into the grid itself, with a little resulting inefficiency. How is this possible? The grid is treated as a structure that repeats, filling space: now any object can be put into the grid, using the grid resolution as a modulus. In other words, something moving out through the left face of the grid "enters" the right face, and its larger location in the world is also noted. By doing so, the whole grid does not have to be recomputed each frame; rather, just the moving objects are deleted and reinserted. Only if the ray traveling through this grid matches the larger location of the object is the object tested for intersection. Paper available at http://www.cs.utah.edu/~reinhard/egwr/
________
"Interval methods for ray casting implicit surfaces with affine arithmetic," Affonso de Cusatis Junior, Luiz Henrique de Figueiredo, Marcelo Gattass, Proceedings of SIBGRAPI'99, p. 65-71. IEEE Computer Press.
Abstract: We study the performance of affine arithmetic as a replacement for interval arithmetic in interval methods for ray casting implicit surfaces. Affine arithmetic is a variant of interval arithmetic designed to handle the dependency problem, and which has improved several interval algorithms in computer graphics.
Full text, color images and other links available at http://www.tecgraf.puc-rio.br/~lhf/sib99/
________
"Hierarchical and Stochastic Algorithms for Radiosity", Philippe Bekaert, K.U. Leuven, PhD Dissertation, 1999.
The radiosity method is a physically based method to compute the illumination in a virtual environment with diffuse (matte) surfaces. It allows to generate very realistic images of such environments by computer, and it is suitable for quantitative predictions of the illumination.
In the radiosity method, a number of simplifying assumptions are made that can however lead to certain image artifacts. In this dissertation, the numerical error introduced by these assumptions is analyzed. The analysis allows to propose new algorithms in which this error, the discretization error, is efficiently controlled during the computations by means of hierarchical refinement.
The radiosity method also requires the solution of very large non-sparse systems of linear equations (about 100,000 equations is common). Moreover, the coefficients of these systems are non-trivial four-dimensional integrals. The main part of this dissertation is devoted to an in-depth study of how the Monte Carlo method can be applied in this context.
The Monte Carlo method is suitable for reliable computation of the coefficients of the systems of equations. It also leads to algorithms that do not require explicit computation and storage of these coefficients. A systematic overview of such algorithms is presented. Previously proposed algorithms of this type are compared and some new algorithms are developed. Next, the application of several variance-reduction techniques is described, and the use of low-discrepancy sampling in this context is discussed. Finally, new ways to incorporate higher-order radiosity approximations and hierarchical refinement are proposed.
The resulting Monte Carlo radiosity algorithms do not only appear to be more reliable, but also often lead more rapidly to usable images than their deterministic counterparts. They require significantly less computer storage, and they are more user friendly. It is expected that these algorithms will stimulate the use of the radiosity method in a wide spectrum of applications.
Overview and thesis at: http://www.cs.kuleuven.ac.be/cwis/research/graphics/CGRG.PUBLICATIONS/PHBPHD
________
"Incoming First-shot for Non-Diffuse Global Illumination," Szirmay-Kalos Laszlo, Mateu Sbert, Roel Martinez, Robert Tobler, Spring Conference of Computer Graphics, Budmerice, 2000
Abstract:
This paper presents a method that can replace the small and medium size lightsources by their effect in non-diffuse global illumination algorithms. Incoming first-shot is a generalization of a preprocessing technique called the first-shot that was developed for speeding up global diffuse radiosity algorithms. In order to reduce the prohibitive memory requirements of the original first-shot when it is applied to non-diffuse scenes in a direct manner, the proposed new method computes and stores only the incoming radiance generated by the lightsources and the reflected radiance is obtained from the incoming radiance on-the-fly taking into account the local BRDF and whether or not the actual viewing direction is in a highlight. Since the radiance function of the reflection is smoother and flatter than the original lightsource function, this replacement makes the integrand of the rendering equation have significantly smaller variation, which can speed up global illumination algorithms. The paper also discusses how the first- shot technique can be built into a stochastic iteration algorithm using ray- bundles, and provides run-time statistics.
Paper at: http://www.fsz.bme.hu/~szirmay/puba.html
________
"3D Visibility, analysis and applications", by Fredo Durand, PhD Dissertation, Universite Joseph Fourier, Grenoble
This thesis deals with 3D visibility, and also contains a huge survey of visibility techniques in different fields such as graphics, vision or robotics.
Abstract: Visibility problems are central to many computer graphics applications. The most common examples include hidden-part removal for view computation, shadow boundaries, mutual visibility of pairs of points, etc. In this document, we first present a theoretical study of 3D visibility properties in the space of light rays. We group rays that see the same object; this defines the 3D visibility complex. The boundaries of these groups of rays correspond to the visual events of the scene (limits of shadows, disappearance of an object when the viewpoint is moved, etc.). We simplify this structure into a graph in line-space which we call the visibility skeleton. Visual events are the arcs of this graph, and our construction algorithm avoids the intricate treatment of the corresponding 1D sets of lines. We simply compute the extremities (lines with 0 degrees of freedom) of these sets, and we topologically deduce the visual events using a catalogue of adjacencies. Our implementation shows that the skeleton is more general, more efficient and more robust than previous techniques. Applied to lighting simulation, the visibility skeleton permits more accurate and more rapid simulations. We have also developed an occlusion culling preprocess for the display of very complex scenes. We compute the set of potentially visible objects with respect to a volumetric region. In this context, our method is the first which handles the cumulative occlusion due to multiple blockers. Our occlusion tests are performed in planes using extended projections, which makes them simple, efficient and robust. In the second part of the document, we present a vast survey of work related to visibility in various domains.
Available at http://graphics.lcs.mit.edu/~fredo/THESE/
back to contents


The investigation follows a series of viral tweets by entrepreneur and web developer David Heinemeier Hansson about algorithms used for the Apple Card, which Goldman Sachs manages in partnership with Apple.
Hansson said the card offered him a credit limit 20 times greater than it gave to his wife, even though she has a higher credit score. He called the algorithm a sexist program.
A spokeswoman for the New York Department of Financial Services confirmed Saturday that the agency will investigate "and ensure all consumers are treated equally regardless of sex."


add note
ack
close
forget
force close
purge
selected incidents
Subject of Last Abnormal Status (if not unknown)
Current
Last Abnormal
Last Abnormal Time
Worst
Actions
Show Details
Action
Alert Key:
Add Note
Ack
Close
Forget
Actions
Body
Events